ce620c1b8b235ef1b3519d5cee592755e6b172bb
[dragonfly.git] / sys / netgraph / pptpgre / ng_pptpgre.c
1
2 /*
3  * ng_pptpgre.c
4  *
5  * Copyright (c) 1996-1999 Whistle Communications, Inc.
6  * All rights reserved.
7  * 
8  * Subject to the following obligations and disclaimer of warranty, use and
9  * redistribution of this software, in source or object code forms, with or
10  * without modifications are expressly permitted by Whistle Communications;
11  * provided, however, that:
12  * 1. Any and all reproductions of the source or object code must include the
13  *    copyright notice above and the following disclaimer of warranties; and
14  * 2. No rights are granted, in any manner or form, to use Whistle
15  *    Communications, Inc. trademarks, including the mark "WHISTLE
16  *    COMMUNICATIONS" on advertising, endorsements, or otherwise except as
17  *    such appears in the above copyright notice or in the software.
18  * 
19  * THIS SOFTWARE IS BEING PROVIDED BY WHISTLE COMMUNICATIONS "AS IS", AND
20  * TO THE MAXIMUM EXTENT PERMITTED BY LAW, WHISTLE COMMUNICATIONS MAKES NO
21  * REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED, REGARDING THIS SOFTWARE,
22  * INCLUDING WITHOUT LIMITATION, ANY AND ALL IMPLIED WARRANTIES OF
23  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, OR NON-INFRINGEMENT.
24  * WHISTLE COMMUNICATIONS DOES NOT WARRANT, GUARANTEE, OR MAKE ANY
25  * REPRESENTATIONS REGARDING THE USE OF, OR THE RESULTS OF THE USE OF THIS
26  * SOFTWARE IN TERMS OF ITS CORRECTNESS, ACCURACY, RELIABILITY OR OTHERWISE.
27  * IN NO EVENT SHALL WHISTLE COMMUNICATIONS BE LIABLE FOR ANY DAMAGES
28  * RESULTING FROM OR ARISING OUT OF ANY USE OF THIS SOFTWARE, INCLUDING
29  * WITHOUT LIMITATION, ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
30  * PUNITIVE, OR CONSEQUENTIAL DAMAGES, PROCUREMENT OF SUBSTITUTE GOODS OR
31  * SERVICES, LOSS OF USE, DATA OR PROFITS, HOWEVER CAUSED AND UNDER ANY
32  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
33  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
34  * THIS SOFTWARE, EVEN IF WHISTLE COMMUNICATIONS IS ADVISED OF THE POSSIBILITY
35  * OF SUCH DAMAGE.
36  *
37  * Author: Archie Cobbs <archie@freebsd.org>
38  *
39  * $FreeBSD: src/sys/netgraph/ng_pptpgre.c,v 1.2.2.13 2002/10/10 18:27:54 archie Exp $
40  * $DragonFly: src/sys/netgraph/pptpgre/ng_pptpgre.c,v 1.7 2005/06/02 22:11:46 swildner Exp $
41  * $Whistle: ng_pptpgre.c,v 1.7 1999/12/08 00:10:06 archie Exp $
42  */
43
44 /*
45  * PPTP/GRE netgraph node type.
46  *
47  * This node type does the GRE encapsulation as specified for the PPTP
48  * protocol (RFC 2637, section 4).  This includes sequencing and
49  * retransmission of frames, but not the actual packet delivery nor
50  * any of the TCP control stream protocol.
51  *
52  * The "upper" hook of this node is suitable for attaching to a "ppp"
53  * node link hook.  The "lower" hook of this node is suitable for attaching
54  * to a "ksocket" node on hook "inet/raw/gre".
55  */
56
57 #include <sys/param.h>
58 #include <sys/systm.h>
59 #include <sys/kernel.h>
60 #include <sys/time.h>
61 #include <sys/conf.h>
62 #include <sys/mbuf.h>
63 #include <sys/malloc.h>
64 #include <sys/errno.h>
65 #include <sys/thread2.h>
66
67 #include <netinet/in.h>
68 #include <netinet/in_systm.h>
69 #include <netinet/ip.h>
70
71 #include <netgraph/ng_message.h>
72 #include <netgraph/netgraph.h>
73 #include <netgraph/ng_parse.h>
74 #include "ng_pptpgre.h"
75
76 /* GRE packet format, as used by PPTP */
77 struct greheader {
78 #if BYTE_ORDER == LITTLE_ENDIAN
79         u_char          recursion:3;            /* recursion control */
80         u_char          ssr:1;                  /* strict source route */
81         u_char          hasSeq:1;               /* sequence number present */
82         u_char          hasKey:1;               /* key present */
83         u_char          hasRoute:1;             /* routing present */
84         u_char          hasSum:1;               /* checksum present */
85         u_char          vers:3;                 /* version */
86         u_char          flags:4;                /* flags */
87         u_char          hasAck:1;               /* acknowlege number present */
88 #elif BYTE_ORDER == BIG_ENDIAN
89         u_char          hasSum:1;               /* checksum present */
90         u_char          hasRoute:1;             /* routing present */
91         u_char          hasKey:1;               /* key present */
92         u_char          hasSeq:1;               /* sequence number present */
93         u_char          ssr:1;                  /* strict source route */
94         u_char          recursion:3;            /* recursion control */
95         u_char          hasAck:1;               /* acknowlege number present */
96         u_char          flags:4;                /* flags */
97         u_char          vers:3;                 /* version */
98 #else
99 #error BYTE_ORDER is not defined properly
100 #endif
101         u_int16_t       proto;                  /* protocol (ethertype) */
102         u_int16_t       length;                 /* payload length */
103         u_int16_t       cid;                    /* call id */
104         u_int32_t       data[0];                /* opt. seq, ack, then data */
105 };
106
107 /* The PPTP protocol ID used in the GRE 'proto' field */
108 #define PPTP_GRE_PROTO          0x880b
109
110 /* Bits that must be set a certain way in all PPTP/GRE packets */
111 #define PPTP_INIT_VALUE         ((0x2001 << 16) | PPTP_GRE_PROTO)
112 #define PPTP_INIT_MASK          0xef7fffff
113
114 /* Min and max packet length */
115 #define PPTP_MAX_PAYLOAD        (0xffff - sizeof(struct greheader) - 8)
116
117 /* All times are scaled by this (PPTP_TIME_SCALE time units = 1 sec.) */
118 #define PPTP_TIME_SCALE         1000                    /* milliseconds */
119 typedef u_int64_t               pptptime_t;
120
121 /* Acknowledgment timeout parameters and functions */
122 #define PPTP_XMIT_WIN           16                      /* max xmit window */
123 #define PPTP_MIN_RTT            (PPTP_TIME_SCALE / 10)  /* 100 milliseconds */
124 #define PPTP_MIN_TIMEOUT        (PPTP_TIME_SCALE / 83)  /* 12 milliseconds */
125 #define PPTP_MAX_TIMEOUT        (10 * PPTP_TIME_SCALE)  /* 10 seconds */
126
127 /* When we recieve a packet, we wait to see if there's an outgoing packet
128    we can piggy-back the ACK off of. These parameters determine the mimimum
129    and maxmimum length of time we're willing to wait in order to do that.
130    These have no effect unless "enableDelayedAck" is turned on. */
131 #define PPTP_MIN_ACK_DELAY      (PPTP_TIME_SCALE / 500) /* 2 milliseconds */
132 #define PPTP_MAX_ACK_DELAY      (PPTP_TIME_SCALE / 2)   /* 500 milliseconds */
133
134 /* See RFC 2637 section 4.4 */
135 #define PPTP_ACK_ALPHA(x)       ((x) >> 3)      /* alpha = 0.125 */
136 #define PPTP_ACK_BETA(x)        ((x) >> 2)      /* beta = 0.25 */
137 #define PPTP_ACK_CHI(x)         ((x) << 2)      /* chi = 4 */
138 #define PPTP_ACK_DELTA(x)       ((x) << 1)      /* delta = 2 */
139
140 #define PPTP_SEQ_DIFF(x,y)      ((int32_t)(x) - (int32_t)(y))
141
142 /* We keep packet retransmit and acknowlegement state in this struct */
143 struct ng_pptpgre_ackp {
144         int32_t                 ato;            /* adaptive time-out value */
145         int32_t                 rtt;            /* round trip time estimate */
146         int32_t                 dev;            /* deviation estimate */
147         u_int16_t               xmitWin;        /* size of xmit window */
148         struct callout          sackTimer;      /* send ack timer */
149         struct callout          rackTimer;      /* recv ack timer */
150         node_p                  *sackTimerPtr;  /* send ack timer pointer */
151         node_p                  *rackTimerPtr;  /* recv ack timer pointer */
152         u_int32_t               winAck;         /* seq when xmitWin will grow */
153         pptptime_t              timeSent[PPTP_XMIT_WIN];
154 #ifdef DEBUG_RAT
155         pptptime_t              timerStart;     /* when rackTimer started */
156         pptptime_t              timerLength;    /* rackTimer duration */
157 #endif
158 };
159
160 /* Node private data */
161 struct ng_pptpgre_private {
162         hook_p                  upper;          /* hook to upper layers */
163         hook_p                  lower;          /* hook to lower layers */
164         struct ng_pptpgre_conf  conf;           /* configuration info */
165         struct ng_pptpgre_ackp  ackp;           /* packet transmit ack state */
166         u_int32_t               recvSeq;        /* last seq # we rcv'd */
167         u_int32_t               xmitSeq;        /* last seq # we sent */
168         u_int32_t               recvAck;        /* last seq # peer ack'd */
169         u_int32_t               xmitAck;        /* last seq # we ack'd */
170         u_int                   timers;         /* number of pending timers */
171         struct timeval          startTime;      /* time node was created */
172         struct ng_pptpgre_stats stats;          /* node statistics */
173 };
174 typedef struct ng_pptpgre_private *priv_p;
175
176 /* Netgraph node methods */
177 static ng_constructor_t ng_pptpgre_constructor;
178 static ng_rcvmsg_t      ng_pptpgre_rcvmsg;
179 static ng_shutdown_t    ng_pptpgre_rmnode;
180 static ng_newhook_t     ng_pptpgre_newhook;
181 static ng_rcvdata_t     ng_pptpgre_rcvdata;
182 static ng_disconnect_t  ng_pptpgre_disconnect;
183
184 /* Helper functions */
185 static int      ng_pptpgre_xmit(node_p node, struct mbuf *m, meta_p meta);
186 static int      ng_pptpgre_recv(node_p node, struct mbuf *m, meta_p meta);
187 static void     ng_pptpgre_start_send_ack_timer(node_p node, int ackTimeout);
188 static void     ng_pptpgre_stop_send_ack_timer(node_p node);
189 static void     ng_pptpgre_start_recv_ack_timer(node_p node);
190 static void     ng_pptpgre_stop_recv_ack_timer(node_p node);
191 static void     ng_pptpgre_recv_ack_timeout(void *arg);
192 static void     ng_pptpgre_send_ack_timeout(void *arg);
193 static void     ng_pptpgre_reset(node_p node);
194 static pptptime_t ng_pptpgre_time(node_p node);
195
196 /* Parse type for struct ng_pptpgre_conf */
197 static const struct ng_parse_struct_field ng_pptpgre_conf_type_fields[]
198         = NG_PPTPGRE_CONF_TYPE_INFO;
199 static const struct ng_parse_type ng_pptpgre_conf_type = {
200         &ng_parse_struct_type,
201         &ng_pptpgre_conf_type_fields,
202 };
203
204 /* Parse type for struct ng_pptpgre_stats */
205 static const struct ng_parse_struct_field ng_pptpgre_stats_type_fields[]
206         = NG_PPTPGRE_STATS_TYPE_INFO;
207 static const struct ng_parse_type ng_pptp_stats_type = {
208         &ng_parse_struct_type,
209         &ng_pptpgre_stats_type_fields
210 };
211
212 /* List of commands and how to convert arguments to/from ASCII */
213 static const struct ng_cmdlist ng_pptpgre_cmdlist[] = {
214         {
215           NGM_PPTPGRE_COOKIE,
216           NGM_PPTPGRE_SET_CONFIG,
217           "setconfig",
218           &ng_pptpgre_conf_type,
219           NULL
220         },
221         {
222           NGM_PPTPGRE_COOKIE,
223           NGM_PPTPGRE_GET_CONFIG,
224           "getconfig",
225           NULL,
226           &ng_pptpgre_conf_type
227         },
228         {
229           NGM_PPTPGRE_COOKIE,
230           NGM_PPTPGRE_GET_STATS,
231           "getstats",
232           NULL,
233           &ng_pptp_stats_type
234         },
235         {
236           NGM_PPTPGRE_COOKIE,
237           NGM_PPTPGRE_CLR_STATS,
238           "clrstats",
239           NULL,
240           NULL
241         },
242         {
243           NGM_PPTPGRE_COOKIE,
244           NGM_PPTPGRE_GETCLR_STATS,
245           "getclrstats",
246           NULL,
247           &ng_pptp_stats_type
248         },
249         { 0 }
250 };
251
252 /* Node type descriptor */
253 static struct ng_type ng_pptpgre_typestruct = {
254         NG_VERSION,
255         NG_PPTPGRE_NODE_TYPE,
256         NULL,
257         ng_pptpgre_constructor,
258         ng_pptpgre_rcvmsg,
259         ng_pptpgre_rmnode,
260         ng_pptpgre_newhook,
261         NULL,
262         NULL,
263         ng_pptpgre_rcvdata,
264         ng_pptpgre_rcvdata,
265         ng_pptpgre_disconnect,
266         ng_pptpgre_cmdlist
267 };
268 NETGRAPH_INIT(pptpgre, &ng_pptpgre_typestruct);
269
270 #define ERROUT(x)       do { error = (x); goto done; } while (0)
271
272 /************************************************************************
273                         NETGRAPH NODE STUFF
274  ************************************************************************/
275
276 /*
277  * Node type constructor
278  */
279 static int
280 ng_pptpgre_constructor(node_p *nodep)
281 {
282         priv_p priv;
283         int error;
284
285         /* Allocate private structure */
286         MALLOC(priv, priv_p, sizeof(*priv), M_NETGRAPH, M_NOWAIT);
287         if (priv == NULL)
288                 return (ENOMEM);
289         bzero(priv, sizeof(*priv));
290
291         /* Call generic node constructor */
292         if ((error = ng_make_node_common(&ng_pptpgre_typestruct, nodep))) {
293                 FREE(priv, M_NETGRAPH);
294                 return (error);
295         }
296         (*nodep)->private = priv;
297
298         /* Initialize state */
299         callout_init(&priv->ackp.sackTimer);
300         callout_init(&priv->ackp.rackTimer);
301
302         /* Done */
303         return (0);
304 }
305
306 /*
307  * Give our OK for a hook to be added.
308  */
309 static int
310 ng_pptpgre_newhook(node_p node, hook_p hook, const char *name)
311 {
312         const priv_p priv = node->private;
313         hook_p *hookPtr;
314
315         /* Check hook name */
316         if (strcmp(name, NG_PPTPGRE_HOOK_UPPER) == 0)
317                 hookPtr = &priv->upper;
318         else if (strcmp(name, NG_PPTPGRE_HOOK_LOWER) == 0)
319                 hookPtr = &priv->lower;
320         else
321                 return (EINVAL);
322
323         /* See if already connected */
324         if (*hookPtr != NULL)
325                 return (EISCONN);
326
327         /* OK */
328         *hookPtr = hook;
329         return (0);
330 }
331
332 /*
333  * Receive a control message.
334  */
335 static int
336 ng_pptpgre_rcvmsg(node_p node, struct ng_mesg *msg,
337               const char *raddr, struct ng_mesg **rptr)
338 {
339         const priv_p priv = node->private;
340         struct ng_mesg *resp = NULL;
341         int error = 0;
342
343         switch (msg->header.typecookie) {
344         case NGM_PPTPGRE_COOKIE:
345                 switch (msg->header.cmd) {
346                 case NGM_PPTPGRE_SET_CONFIG:
347                     {
348                         struct ng_pptpgre_conf *const newConf =
349                                 (struct ng_pptpgre_conf *) msg->data;
350
351                         /* Check for invalid or illegal config */
352                         if (msg->header.arglen != sizeof(*newConf))
353                                 ERROUT(EINVAL);
354                         ng_pptpgre_reset(node);         /* reset on configure */
355                         priv->conf = *newConf;
356                         break;
357                     }
358                 case NGM_PPTPGRE_GET_CONFIG:
359                         NG_MKRESPONSE(resp, msg, sizeof(priv->conf), M_NOWAIT);
360                         if (resp == NULL)
361                                 ERROUT(ENOMEM);
362                         bcopy(&priv->conf, resp->data, sizeof(priv->conf));
363                         break;
364                 case NGM_PPTPGRE_GET_STATS:
365                 case NGM_PPTPGRE_CLR_STATS:
366                 case NGM_PPTPGRE_GETCLR_STATS:
367                     {
368                         if (msg->header.cmd != NGM_PPTPGRE_CLR_STATS) {
369                                 NG_MKRESPONSE(resp, msg,
370                                     sizeof(priv->stats), M_NOWAIT);
371                                 if (resp == NULL)
372                                         ERROUT(ENOMEM);
373                                 bcopy(&priv->stats,
374                                     resp->data, sizeof(priv->stats));
375                         }
376                         if (msg->header.cmd != NGM_PPTPGRE_GET_STATS)
377                                 bzero(&priv->stats, sizeof(priv->stats));
378                         break;
379                     }
380                 default:
381                         error = EINVAL;
382                         break;
383                 }
384                 break;
385         default:
386                 error = EINVAL;
387                 break;
388         }
389         if (rptr)
390                 *rptr = resp;
391         else if (resp)
392                 FREE(resp, M_NETGRAPH);
393
394 done:
395         FREE(msg, M_NETGRAPH);
396         return (error);
397 }
398
399 /*
400  * Receive incoming data on a hook.
401  */
402 static int
403 ng_pptpgre_rcvdata(hook_p hook, struct mbuf *m, meta_p meta)
404 {
405         const node_p node = hook->node;
406         const priv_p priv = node->private;
407
408         /* If not configured, reject */
409         if (!priv->conf.enabled) {
410                 NG_FREE_DATA(m, meta);
411                 return (ENXIO);
412         }
413
414         /* Treat as xmit or recv data */
415         if (hook == priv->upper)
416                 return ng_pptpgre_xmit(node, m, meta);
417         if (hook == priv->lower)
418                 return ng_pptpgre_recv(node, m, meta);
419         panic("%s: weird hook", __func__);
420 }
421
422 /*
423  * Destroy node
424  */
425 static int
426 ng_pptpgre_rmnode(node_p node)
427 {
428         const priv_p priv = node->private;
429
430         /* Reset node */
431         ng_pptpgre_reset(node);
432
433         /* Take down netgraph node */
434         node->flags |= NG_INVALID;
435         ng_cutlinks(node);
436         ng_unname(node);
437
438         /* If no timers remain, free private info as well */
439         if (priv->timers == 0) {
440                 FREE(priv, M_NETGRAPH);
441                 node->private = NULL;
442         }
443
444         /* Done */
445         ng_unref(node);
446         return (0);
447 }
448
449 /*
450  * Hook disconnection
451  */
452 static int
453 ng_pptpgre_disconnect(hook_p hook)
454 {
455         const node_p node = hook->node;
456         const priv_p priv = node->private;
457
458         /* Zero out hook pointer */
459         if (hook == priv->upper)
460                 priv->upper = NULL;
461         else if (hook == priv->lower)
462                 priv->lower = NULL;
463         else
464                 panic("%s: unknown hook", __func__);
465
466         /* Go away if no longer connected to anything */
467         if (node->numhooks == 0)
468                 ng_rmnode(node);
469         return (0);
470 }
471
472 /*************************************************************************
473                     TRANSMIT AND RECEIVE FUNCTIONS
474 *************************************************************************/
475
476 /*
477  * Transmit an outgoing frame, or just an ack if m is NULL.
478  */
479 static int
480 ng_pptpgre_xmit(node_p node, struct mbuf *m, meta_p meta)
481 {
482         const priv_p priv = node->private;
483         struct ng_pptpgre_ackp *const a = &priv->ackp;
484         u_char buf[sizeof(struct greheader) + 2 * sizeof(u_int32_t)];
485         struct greheader *const gre = (struct greheader *)buf;
486         int grelen, error;
487
488         /* Check if there's data */
489         if (m != NULL) {
490
491                 /* Is our transmit window full? */
492                 if ((u_int32_t)PPTP_SEQ_DIFF(priv->xmitSeq, priv->recvAck)
493                       >= a->xmitWin) {
494                         priv->stats.xmitDrops++;
495                         NG_FREE_DATA(m, meta);
496                         return (ENOBUFS);
497                 }
498
499                 /* Sanity check frame length */
500                 if (m != NULL && m->m_pkthdr.len > PPTP_MAX_PAYLOAD) {
501                         priv->stats.xmitTooBig++;
502                         NG_FREE_DATA(m, meta);
503                         return (EMSGSIZE);
504                 }
505         } else
506                 priv->stats.xmitLoneAcks++;
507
508         /* Build GRE header */
509         ((u_int32_t *)gre)[0] = htonl(PPTP_INIT_VALUE);
510         gre->length = (m != NULL) ? htons((u_short)m->m_pkthdr.len) : 0;
511         gre->cid = htons(priv->conf.peerCid);
512
513         /* Include sequence number if packet contains any data */
514         if (m != NULL) {
515                 gre->hasSeq = 1;
516                 a->timeSent[priv->xmitSeq - priv->recvAck]
517                     = ng_pptpgre_time(node);
518                 priv->xmitSeq++;
519                 gre->data[0] = htonl(priv->xmitSeq);
520         }
521
522         /* Include acknowledgement (and stop send ack timer) if needed */
523         if (priv->conf.enableAlwaysAck || priv->xmitAck != priv->recvSeq) {
524                 gre->hasAck = 1;
525                 gre->data[gre->hasSeq] = htonl(priv->recvSeq);
526                 priv->xmitAck = priv->recvSeq;
527                 ng_pptpgre_stop_send_ack_timer(node);
528         }
529
530         /* Prepend GRE header to outgoing frame */
531         grelen = sizeof(*gre) + sizeof(u_int32_t) * (gre->hasSeq + gre->hasAck);
532         if (m == NULL) {
533                 MGETHDR(m, MB_DONTWAIT, MT_DATA);
534                 if (m == NULL) {
535                         priv->stats.memoryFailures++;
536                         NG_FREE_META(meta);
537                         return (ENOBUFS);
538                 }
539                 m->m_len = m->m_pkthdr.len = grelen;
540                 m->m_pkthdr.rcvif = NULL;
541         } else {
542                 M_PREPEND(m, grelen, MB_DONTWAIT);
543                 if (m == NULL || (m->m_len < grelen
544                     && (m = m_pullup(m, grelen)) == NULL)) {
545                         priv->stats.memoryFailures++;
546                         NG_FREE_META(meta);
547                         return (ENOBUFS);
548                 }
549         }
550         bcopy(gre, mtod(m, u_char *), grelen);
551
552         /* Update stats */
553         priv->stats.xmitPackets++;
554         priv->stats.xmitOctets += m->m_pkthdr.len;
555
556         /* Deliver packet */
557         NG_SEND_DATA(error, priv->lower, m, meta);
558
559         /* Start receive ACK timer if data was sent and not already running */
560         if (error == 0 && gre->hasSeq && priv->xmitSeq == priv->recvAck + 1)
561                 ng_pptpgre_start_recv_ack_timer(node);
562         return (error);
563 }
564
565 /*
566  * Handle an incoming packet.  The packet includes the IP header.
567  */
568 static int
569 ng_pptpgre_recv(node_p node, struct mbuf *m, meta_p meta)
570 {
571         const priv_p priv = node->private;
572         int iphlen, grelen, extralen;
573         const struct greheader *gre;
574         const struct ip *ip;
575         int error = 0;
576
577         /* Update stats */
578         priv->stats.recvPackets++;
579         priv->stats.recvOctets += m->m_pkthdr.len;
580
581         /* Sanity check packet length */
582         if (m->m_pkthdr.len < sizeof(*ip) + sizeof(*gre)) {
583                 priv->stats.recvRunts++;
584 bad:
585                 NG_FREE_DATA(m, meta);
586                 return (EINVAL);
587         }
588
589         /* Safely pull up the complete IP+GRE headers */
590         if (m->m_len < sizeof(*ip) + sizeof(*gre)
591             && (m = m_pullup(m, sizeof(*ip) + sizeof(*gre))) == NULL) {
592                 priv->stats.memoryFailures++;
593                 NG_FREE_META(meta);
594                 return (ENOBUFS);
595         }
596         ip = mtod(m, const struct ip *);
597         iphlen = ip->ip_hl << 2;
598         if (m->m_len < iphlen + sizeof(*gre)) {
599                 if ((m = m_pullup(m, iphlen + sizeof(*gre))) == NULL) {
600                         priv->stats.memoryFailures++;
601                         NG_FREE_META(meta);
602                         return (ENOBUFS);
603                 }
604                 ip = mtod(m, const struct ip *);
605         }
606         gre = (const struct greheader *)((const u_char *)ip + iphlen);
607         grelen = sizeof(*gre) + sizeof(u_int32_t) * (gre->hasSeq + gre->hasAck);
608         if (m->m_pkthdr.len < iphlen + grelen) {
609                 priv->stats.recvRunts++;
610                 goto bad;
611         }
612         if (m->m_len < iphlen + grelen) {
613                 if ((m = m_pullup(m, iphlen + grelen)) == NULL) {
614                         priv->stats.memoryFailures++;
615                         NG_FREE_META(meta);
616                         return (ENOBUFS);
617                 }
618                 ip = mtod(m, const struct ip *);
619                 gre = (const struct greheader *)((const u_char *)ip + iphlen);
620         }
621
622         /* Sanity check packet length and GRE header bits */
623         extralen = m->m_pkthdr.len
624             - (iphlen + grelen + gre->hasSeq * (u_int16_t)ntohs(gre->length));
625         if (extralen < 0) {
626                 priv->stats.recvBadGRE++;
627                 goto bad;
628         }
629         if ((ntohl(*((const u_int32_t *)gre)) & PPTP_INIT_MASK)
630             != PPTP_INIT_VALUE) {
631                 priv->stats.recvBadGRE++;
632                 goto bad;
633         }
634         if (ntohs(gre->cid) != priv->conf.cid) {
635                 priv->stats.recvBadCID++;
636                 goto bad;
637         }
638
639         /* Look for peer ack */
640         if (gre->hasAck) {
641                 struct ng_pptpgre_ackp *const a = &priv->ackp;
642                 const u_int32_t ack = ntohl(gre->data[gre->hasSeq]);
643                 const int index = ack - priv->recvAck - 1;
644                 long sample;
645                 long diff;
646
647                 /* Sanity check ack value */
648                 if (PPTP_SEQ_DIFF(ack, priv->xmitSeq) > 0) {
649                         priv->stats.recvBadAcks++;
650                         goto badAck;            /* we never sent it! */
651                 }
652                 if (PPTP_SEQ_DIFF(ack, priv->recvAck) <= 0)
653                         goto badAck;            /* ack already timed out */
654                 priv->recvAck = ack;
655
656                 /* Update adaptive timeout stuff */
657                 sample = ng_pptpgre_time(node) - a->timeSent[index];
658                 diff = sample - a->rtt;
659                 a->rtt += PPTP_ACK_ALPHA(diff);
660                 if (diff < 0)
661                         diff = -diff;
662                 a->dev += PPTP_ACK_BETA(diff - a->dev);
663                 a->ato = a->rtt + PPTP_ACK_CHI(a->dev);
664                 if (a->ato > PPTP_MAX_TIMEOUT)
665                         a->ato = PPTP_MAX_TIMEOUT;
666                 if (a->ato < PPTP_MIN_TIMEOUT)
667                         a->ato = PPTP_MIN_TIMEOUT;
668
669                 /* Shift packet transmit times in our transmit window */
670                 ovbcopy(a->timeSent + index + 1, a->timeSent,
671                     sizeof(*a->timeSent) * (PPTP_XMIT_WIN - (index + 1)));
672
673                 /* If we sent an entire window, increase window size by one */
674                 if (PPTP_SEQ_DIFF(ack, a->winAck) >= 0
675                     && a->xmitWin < PPTP_XMIT_WIN) {
676                         a->xmitWin++;
677                         a->winAck = ack + a->xmitWin;
678                 }
679
680                 /* Stop/(re)start receive ACK timer as necessary */
681                 ng_pptpgre_stop_recv_ack_timer(node);
682                 if (priv->recvAck != priv->xmitSeq)
683                         ng_pptpgre_start_recv_ack_timer(node);
684         }
685 badAck:
686
687         /* See if frame contains any data */
688         if (gre->hasSeq) {
689                 struct ng_pptpgre_ackp *const a = &priv->ackp;
690                 const u_int32_t seq = ntohl(gre->data[0]);
691
692                 /* Sanity check sequence number */
693                 if (PPTP_SEQ_DIFF(seq, priv->recvSeq) <= 0) {
694                         if (seq == priv->recvSeq)
695                                 priv->stats.recvDuplicates++;
696                         else
697                                 priv->stats.recvOutOfOrder++;
698                         goto bad;               /* out-of-order or dup */
699                 }
700                 priv->recvSeq = seq;
701
702                 /* We need to acknowledge this packet; do it soon... */
703                 if (a->sackTimerPtr == NULL) {
704                         int maxWait;
705
706                         /* Take 1/4 of the estimated round trip time */
707                         maxWait = (a->rtt >> 2);
708
709                         /* If delayed ACK is disabled, send it now */
710                         if (!priv->conf.enableDelayedAck)       /* ack now */
711                                 ng_pptpgre_xmit(node, NULL, NULL);
712                         else {                                  /* ack later */
713                                 if (maxWait < PPTP_MIN_ACK_DELAY)
714                                         maxWait = PPTP_MIN_ACK_DELAY;
715                                 if (maxWait > PPTP_MAX_ACK_DELAY)
716                                         maxWait = PPTP_MAX_ACK_DELAY;
717                                 ng_pptpgre_start_send_ack_timer(node, maxWait);
718                         }
719                 }
720
721                 /* Trim mbuf down to internal payload */
722                 m_adj(m, iphlen + grelen);
723                 if (extralen > 0)
724                         m_adj(m, -extralen);
725
726                 /* Deliver frame to upper layers */
727                 NG_SEND_DATA(error, priv->upper, m, meta);
728         } else {
729                 priv->stats.recvLoneAcks++;
730                 NG_FREE_DATA(m, meta);          /* no data to deliver */
731         }
732         return (error);
733 }
734
735 /*************************************************************************
736                     TIMER RELATED FUNCTIONS
737 *************************************************************************/
738
739 /*
740  * Start a timer for the peer's acknowledging our oldest unacknowledged
741  * sequence number.  If we get an ack for this sequence number before
742  * the timer goes off, we cancel the timer.  Resets currently running
743  * recv ack timer, if any.
744  */
745 static void
746 ng_pptpgre_start_recv_ack_timer(node_p node)
747 {
748         const priv_p priv = node->private;
749         struct ng_pptpgre_ackp *const a = &priv->ackp;
750         int remain, ticks;
751
752         /* Compute how long until oldest unack'd packet times out,
753            and reset the timer to that time. */
754         KASSERT(a->rackTimerPtr == NULL, ("%s: rackTimer", __func__));
755         remain = (a->timeSent[0] + a->ato) - ng_pptpgre_time(node);
756         if (remain < 0)
757                 remain = 0;
758 #ifdef DEBUG_RAT
759         a->timerLength = remain;
760         a->timerStart = ng_pptpgre_time(node);
761 #endif
762
763         /* Start new timer */
764         MALLOC(a->rackTimerPtr, node_p *, sizeof(node_p), M_NETGRAPH, M_NOWAIT);
765         if (a->rackTimerPtr == NULL) {
766                 priv->stats.memoryFailures++;
767                 return;                 /* XXX potential hang here */
768         }
769         *a->rackTimerPtr = node;        /* ensures the correct timeout event */
770         node->refs++;
771         priv->timers++;
772
773         /* Be conservative: timeout can happen up to 1 tick early */
774         ticks = (((remain * hz) + PPTP_TIME_SCALE - 1) / PPTP_TIME_SCALE) + 1;
775         callout_reset(&a->rackTimer, ticks,
776             ng_pptpgre_recv_ack_timeout, a->rackTimerPtr);
777 }
778
779 /*
780  * Stop receive ack timer.
781  */
782 static void
783 ng_pptpgre_stop_recv_ack_timer(node_p node)
784 {
785         const priv_p priv = node->private;
786         struct ng_pptpgre_ackp *const a = &priv->ackp;
787
788         if (callout_stop(&a->rackTimer)) {
789                 FREE(a->rackTimerPtr, M_NETGRAPH);
790                 priv->timers--;
791                 ng_unref(node);
792         }
793         a->rackTimerPtr = NULL;
794 }
795
796 /*
797  * The peer has failed to acknowledge the oldest unacknowledged sequence
798  * number within the time allotted.  Update our adaptive timeout parameters
799  * and reset/restart the recv ack timer.
800  */
801 static void
802 ng_pptpgre_recv_ack_timeout(void *arg)
803 {
804         const node_p node = *((node_p *)arg);
805         const priv_p priv = node->private;
806         struct ng_pptpgre_ackp *const a = &priv->ackp;
807
808         crit_enter();
809         /* This complicated stuff is needed to avoid race conditions */
810         FREE(arg, M_NETGRAPH);
811         KASSERT(node->refs > 0, ("%s: no refs", __func__));
812         KASSERT(priv != NULL, ("%s: priv=NULL", __func__));
813         priv->timers--;
814         if ((node->flags & NG_INVALID) != 0) {  /* shutdown race condition */
815                 if (priv->timers == 0) {
816                         FREE(priv, M_NETGRAPH);
817                         node->private = NULL;
818                 }
819                 ng_unref(node);
820                 crit_exit();
821                 return;
822         }
823         if (arg != a->rackTimerPtr) {   /* timer stopped race condition */
824                 ng_unref(node);
825                 crit_exit();
826                 return;
827         }
828         a->rackTimerPtr = NULL;
829
830         /* Update adaptive timeout stuff */
831         priv->stats.recvAckTimeouts++;
832         a->rtt = PPTP_ACK_DELTA(a->rtt);
833         a->ato = a->rtt + PPTP_ACK_CHI(a->dev);
834         if (a->ato > PPTP_MAX_TIMEOUT)
835                 a->ato = PPTP_MAX_TIMEOUT;
836         if (a->ato < PPTP_MIN_TIMEOUT)
837                 a->ato = PPTP_MIN_TIMEOUT;
838
839 #ifdef DEBUG_RAT
840     log(LOG_DEBUG,
841         "RAT now=%d seq=0x%x sent=%d tstart=%d tlen=%d ato=%d\n",
842         (int)ng_pptpgre_time(node), priv->recvAck + 1,
843         (int)a->timeSent[0], (int)a->timerStart, (int)a->timerLength, a->ato);
844 #endif
845
846         /* Reset ack and sliding window */
847         priv->recvAck = priv->xmitSeq;          /* pretend we got the ack */
848         a->xmitWin = (a->xmitWin + 1) / 2;      /* shrink transmit window */
849         a->winAck = priv->recvAck + a->xmitWin; /* reset win expand time */
850         ng_unref(node);
851         crit_exit();
852 }
853
854 /*
855  * Start the send ack timer. This assumes the timer is not
856  * already running.
857  */
858 static void
859 ng_pptpgre_start_send_ack_timer(node_p node, int ackTimeout)
860 {
861         const priv_p priv = node->private;
862         struct ng_pptpgre_ackp *const a = &priv->ackp;
863         int ticks;
864
865         /* Start new timer */
866         KASSERT(a->sackTimerPtr == NULL, ("%s: sackTimer", __func__));
867         MALLOC(a->sackTimerPtr, node_p *, sizeof(node_p), M_NETGRAPH, M_NOWAIT);
868         if (a->sackTimerPtr == NULL) {
869                 priv->stats.memoryFailures++;
870                 return;                 /* XXX potential hang here */
871         }
872         *a->sackTimerPtr = node;        /* ensures the correct timeout event */
873         node->refs++;
874         priv->timers++;
875
876         /* Be conservative: timeout can happen up to 1 tick early */
877         ticks = (((ackTimeout * hz) + PPTP_TIME_SCALE - 1) / PPTP_TIME_SCALE);
878         callout_reset(&a->sackTimer, ticks,
879             ng_pptpgre_send_ack_timeout, a->sackTimerPtr);
880 }
881
882 /*
883  * Stop send ack timer.
884  */
885 static void
886 ng_pptpgre_stop_send_ack_timer(node_p node)
887 {
888         const priv_p priv = node->private;
889         struct ng_pptpgre_ackp *const a = &priv->ackp;
890
891         if (callout_stop(&a->sackTimer)) {
892                 FREE(a->sackTimerPtr, M_NETGRAPH);
893                 priv->timers--;
894                 ng_unref(node);
895         }
896         a->sackTimerPtr = NULL;
897 }
898
899 /*
900  * We've waited as long as we're willing to wait before sending an
901  * acknowledgement to the peer for received frames. We had hoped to
902  * be able to piggy back our acknowledgement on an outgoing data frame,
903  * but apparently there haven't been any since. So send the ack now.
904  */
905 static void
906 ng_pptpgre_send_ack_timeout(void *arg)
907 {
908         const node_p node = *((node_p *)arg);
909         const priv_p priv = node->private;
910         struct ng_pptpgre_ackp *const a = &priv->ackp;
911
912         crit_enter();
913         /* This complicated stuff is needed to avoid race conditions */
914         FREE(arg, M_NETGRAPH);
915         KASSERT(node->refs > 0, ("%s: no refs", __func__));
916         KASSERT(priv != NULL, ("%s: priv=NULL", __func__));
917         priv->timers--;
918         if ((node->flags & NG_INVALID) != 0) {  /* shutdown race condition */
919                 if (priv->timers == 0) {
920                         FREE(priv, M_NETGRAPH);
921                         node->private = NULL;
922                 }
923                 ng_unref(node);
924                 crit_exit();
925                 return;
926         }
927         if (a->sackTimerPtr != arg) {   /* timer stopped race condition */
928                 ng_unref(node);
929                 crit_exit();
930                 return;
931         }
932         a->sackTimerPtr = NULL;
933
934         /* Send a frame with an ack but no payload */
935         ng_pptpgre_xmit(node, NULL, NULL);
936         ng_unref(node);
937         crit_exit();
938 }
939
940 /*************************************************************************
941                     MISC FUNCTIONS
942 *************************************************************************/
943
944 /*
945  * Reset state
946  */
947 static void
948 ng_pptpgre_reset(node_p node)
949 {
950         const priv_p priv = node->private;
951         struct ng_pptpgre_ackp *const a = &priv->ackp;
952
953         /* Reset adaptive timeout state */
954         a->ato = PPTP_MAX_TIMEOUT;
955         a->rtt = priv->conf.peerPpd * PPTP_TIME_SCALE / 10;  /* ppd in 10ths */
956         if (a->rtt < PPTP_MIN_RTT)
957                 a->rtt = PPTP_MIN_RTT;
958         a->dev = 0;
959         a->xmitWin = (priv->conf.recvWin + 1) / 2;
960         if (a->xmitWin < 2)             /* often the first packet is lost */
961                 a->xmitWin = 2;         /*   because the peer isn't ready */
962         if (a->xmitWin > PPTP_XMIT_WIN)
963                 a->xmitWin = PPTP_XMIT_WIN;
964         a->winAck = a->xmitWin;
965
966         /* Reset sequence numbers */
967         priv->recvSeq = ~0;
968         priv->recvAck = ~0;
969         priv->xmitSeq = ~0;
970         priv->xmitAck = ~0;
971
972         /* Reset start time */
973         getmicrouptime(&priv->startTime);
974
975         /* Reset stats */
976         bzero(&priv->stats, sizeof(priv->stats));
977
978         /* Stop timers */
979         ng_pptpgre_stop_send_ack_timer(node);
980         ng_pptpgre_stop_recv_ack_timer(node);
981 }
982
983 /*
984  * Return the current time scaled & translated to our internally used format.
985  */
986 static pptptime_t
987 ng_pptpgre_time(node_p node)
988 {
989         const priv_p priv = node->private;
990         struct timeval tv;
991         pptptime_t t;
992
993         microuptime(&tv);
994         if (tv.tv_sec < priv->startTime.tv_sec
995             || (tv.tv_sec == priv->startTime.tv_sec
996               && tv.tv_usec < priv->startTime.tv_usec))
997                 return (0);
998         timevalsub(&tv, &priv->startTime);
999         t = (pptptime_t)tv.tv_sec * PPTP_TIME_SCALE;
1000         t += (pptptime_t)tv.tv_usec / (1000000 / PPTP_TIME_SCALE);
1001         return(t);
1002 }
1003