Constants needed for printing.
[akaros.git] / kern / src / net / rudp.c
1 /*
2  *  This protocol is compatible with UDP's packet format.
3  *  It could be done over UDP if need be.
4  */
5 #include        "u.h"
6 #include        "../port/lib.h"
7 #include        "mem.h"
8 #include        "dat.h"
9 #include        "fns.h"
10 #include        "../port/error.h"
11
12 #include        "ip.h"
13
14 #define DEBUG   0
15 #define DPRINT if(DEBUG)print
16
17 #define SEQDIFF(a,b) ( (a)>=(b)?\
18                         (a)-(b):\
19                         0xffffffffUL-((b)-(a)) )
20 #define INSEQ(a,start,end) ( (start)<=(end)?\
21                                 ((a)>(start)&&(a)<=(end)):\
22                                 ((a)>(start)||(a)<=(end)) )
23 #define UNACKED(r) SEQDIFF(r->sndseq, r->ackrcvd)
24 #define NEXTSEQ(a) ( (a)+1 == 0 ? 1 : (a)+1 )
25
26 enum
27 {
28         UDP_HDRSIZE     = 20,   /* pseudo header + udp header */
29         UDP_PHDRSIZE    = 12,   /* pseudo header */
30         UDP_RHDRSIZE    = 36,   /* pseudo header + udp header + rudp header */
31         UDP_IPHDR       = 8,    /* ip header */
32         IP_UDPPROTO     = 254,
33         UDP_USEAD7      = 52,
34         UDP_USEAD6      = 36,
35         UDP_USEAD4      = 12,
36
37         Rudprxms        = 200,
38         Rudptickms      = 50,
39         Rudpmaxxmit     = 10,
40         Maxunacked      = 100,
41
42 };
43
44 #define Hangupgen       0xffffffff      /* used only in hangup messages */
45
46 typedef struct Udphdr Udphdr;
47 struct Udphdr
48 {
49         /* ip header */
50         uchar   vihl;           /* Version and header length */
51         uchar   tos;            /* Type of service */
52         uchar   length[2];      /* packet length */
53         uchar   id[2];          /* Identification */
54         uchar   frag[2];        /* Fragment information */
55
56         /* pseudo header starts here */
57         uchar   Unused;
58         uchar   udpproto;       /* Protocol */
59         uchar   udpplen[2];     /* Header plus data length */
60         uchar   udpsrc[4];      /* Ip source */
61         uchar   udpdst[4];      /* Ip destination */
62
63         /* udp header */
64         uchar   udpsport[2];    /* Source port */
65         uchar   udpdport[2];    /* Destination port */
66         uchar   udplen[2];      /* data length */
67         uchar   udpcksum[2];    /* Checksum */
68 };
69
70 typedef struct Rudphdr Rudphdr;
71 struct Rudphdr
72 {
73         /* ip header */
74         uchar   vihl;           /* Version and header length */
75         uchar   tos;            /* Type of service */
76         uchar   length[2];      /* packet length */
77         uchar   id[2];          /* Identification */
78         uchar   frag[2];        /* Fragment information */
79
80         /* pseudo header starts here */
81         uchar   Unused;
82         uchar   udpproto;       /* Protocol */
83         uchar   udpplen[2];     /* Header plus data length */
84         uchar   udpsrc[4];      /* Ip source */
85         uchar   udpdst[4];      /* Ip destination */
86
87         /* udp header */
88         uchar   udpsport[2];    /* Source port */
89         uchar   udpdport[2];    /* Destination port */
90         uchar   udplen[2];      /* data length (includes rudp header) */
91         uchar   udpcksum[2];    /* Checksum */
92
93         /* rudp header */
94         uchar   relseq[4];      /* id of this packet (or 0) */
95         uchar   relsgen[4];     /* generation/time stamp */
96         uchar   relack[4];      /* packet being acked (or 0) */
97         uchar   relagen[4];     /* generation/time stamp */
98 };
99
100
101 /*
102  *  one state structure per destination
103  */
104 typedef struct Reliable Reliable;
105 struct Reliable
106 {
107         Ref;
108
109         Reliable *next;
110
111         uchar   addr[IPaddrlen];        /* always V6 when put here */
112         ushort  port;
113
114         Block   *unacked;       /* unacked msg list */
115         Block   *unackedtail;   /*  and its tail */
116
117         int     timeout;        /* time since first unacked msg sent */
118         int     xmits;          /* number of times first unacked msg sent */
119
120         ulong   sndseq;         /* next packet to be sent */
121         ulong   sndgen;         /*  and its generation */
122
123         ulong   rcvseq;         /* last packet received */
124         ulong   rcvgen;         /*  and its generation */
125
126         ulong   acksent;        /* last ack sent */
127         ulong   ackrcvd;        /* last msg for which ack was rcvd */
128
129         /* flow control */
130         QLock   lock;
131         Rendez  vous;
132         int     blocked;
133 };
134
135
136
137 /* MIB II counters */
138 typedef struct Rudpstats Rudpstats;
139 struct Rudpstats
140 {
141         ulong   rudpInDatagrams;
142         ulong   rudpNoPorts;
143         ulong   rudpInErrors;
144         ulong   rudpOutDatagrams;
145 };
146
147 typedef struct Rudppriv Rudppriv;
148 struct Rudppriv
149 {
150         Ipht    ht;
151
152         /* MIB counters */
153         Rudpstats       ustats;
154
155         /* non-MIB stats */
156         ulong   csumerr;                /* checksum errors */
157         ulong   lenerr;                 /* short packet */
158         ulong   rxmits;                 /* # of retransmissions */
159         ulong   orders;                 /* # of out of order pkts */
160
161         /* keeping track of the ack kproc */
162         int     ackprocstarted;
163         QLock   apl;
164 };
165
166
167 static ulong generation = 0;
168 static Rendez rend;
169
170 /*
171  *  protocol specific part of Conv
172  */
173 typedef struct Rudpcb Rudpcb;
174 struct Rudpcb
175 {
176         QLock;
177         uchar   headers;
178         uchar   randdrop;
179         Reliable *r;
180 };
181
182 /*
183  * local functions 
184  */
185 void    relsendack(Conv*, Reliable*, int);
186 int     reliput(Conv*, Block*, uchar*, ushort);
187 Reliable *relstate(Rudpcb*, uchar*, ushort, char*);
188 void    relput(Reliable*);
189 void    relforget(Conv *, uchar*, int, int);
190 void    relackproc(void *);
191 void    relackq(Reliable *, Block*);
192 void    relhangup(Conv *, Reliable*);
193 void    relrexmit(Conv *, Reliable*);
194 void    relput(Reliable*);
195 void    rudpkick(void *x);
196
197 static void
198 rudpstartackproc(Proto *rudp)
199 {
200         Rudppriv *rpriv;
201         char kpname[KNAMELEN];
202
203         rpriv = rudp->priv;
204         if(rpriv->ackprocstarted == 0){
205                 qlock(&rpriv->apl);
206                 if(rpriv->ackprocstarted == 0){
207                         sprint(kpname, "#I%drudpack", rudp->f->dev);
208                         kproc(kpname, relackproc, rudp, 0);
209                         rpriv->ackprocstarted = 1;
210                 }
211                 qunlock(&rpriv->apl);
212         }
213 }
214
215 static char*
216 rudpconnect(Conv *c, char **argv, int argc)
217 {
218         char *e;
219         Rudppriv *upriv;
220
221         upriv = c->p->priv;
222         rudpstartackproc(c->p);
223         e = Fsstdconnect(c, argv, argc);
224         Fsconnected(c, e);
225         iphtadd(&upriv->ht, c);
226
227         return e;
228 }
229
230
231 static int
232 rudpstate(Conv *c, char *state, int n)
233 {
234         Rudpcb *ucb;
235         Reliable *r;
236         int m;
237
238         m = snprint(state, n, "%s", c->inuse?"Open":"Closed");
239         ucb = (Rudpcb*)c->ptcl;
240         qlock(ucb);
241         for(r = ucb->r; r; r = r->next)
242                 m += snprint(state+m, n-m, " %I/%ld", r->addr, UNACKED(r));
243         qunlock(ucb);
244         return m;
245 }
246
247 static char*
248 rudpannounce(Conv *c, char** argv, int argc)
249 {
250         char *e;
251         Rudppriv *upriv;
252
253         upriv = c->p->priv;
254         rudpstartackproc(c->p);
255         e = Fsstdannounce(c, argv, argc);
256         if(e != nil)
257                 return e;
258         Fsconnected(c, nil);
259         iphtadd(&upriv->ht, c);
260
261         return nil;
262 }
263
264 static void
265 rudpcreate(Conv *c)
266 {
267         c->rq = qopen(64*1024, Qmsg, 0, 0);
268         c->wq = qopen(64*1024, Qkick, rudpkick, c);
269 }
270
271 static void
272 rudpclose(Conv *c)
273 {
274         Rudpcb *ucb;
275         Reliable *r, *nr;
276         Rudppriv *upriv;
277
278         upriv = c->p->priv;
279         iphtrem(&upriv->ht, c);
280
281         /* force out any delayed acks */
282         ucb = (Rudpcb*)c->ptcl;
283         qlock(ucb);
284         for(r = ucb->r; r; r = r->next){
285                 if(r->acksent != r->rcvseq)
286                         relsendack(c, r, 0);
287         }
288         qunlock(ucb);
289
290         qclose(c->rq);
291         qclose(c->wq);
292         qclose(c->eq);
293         ipmove(c->laddr, IPnoaddr);
294         ipmove(c->raddr, IPnoaddr);
295         c->lport = 0;
296         c->rport = 0;
297
298         ucb->headers = 0;
299         ucb->randdrop = 0;
300         qlock(ucb);
301         for(r = ucb->r; r; r = nr){
302                 if(r->acksent != r->rcvseq)
303                         relsendack(c, r, 0);
304                 nr = r->next;
305                 relhangup(c, r);
306                 relput(r);
307         }
308         ucb->r = 0;
309
310         qunlock(ucb);
311 }
312
313 /*
314  *  randomly don't send packets
315  */
316 static void
317 doipoput(Conv *c, Fs *f, Block *bp, int x, int ttl, int tos)
318 {
319         Rudpcb *ucb;
320
321         ucb = (Rudpcb*)c->ptcl;
322         if(ucb->randdrop && nrand(100) < ucb->randdrop)
323                 freeblist(bp);
324         else
325                 ipoput4(f, bp, x, ttl, tos, nil);
326 }
327
328 int
329 flow(void *v)
330 {
331         Reliable *r = v;
332
333         return UNACKED(r) <= Maxunacked;
334 }
335
336 void
337 rudpkick(void *x)
338 {
339         Conv *c = x;
340         Udphdr *uh;
341         ushort rport;
342         uchar laddr[IPaddrlen], raddr[IPaddrlen];
343         Block *bp;
344         Rudpcb *ucb;
345         Rudphdr *rh;
346         Reliable *r;
347         int dlen, ptcllen;
348         Rudppriv *upriv;
349         Fs *f;
350
351         upriv = c->p->priv;
352         f = c->p->f;
353
354         netlog(c->p->f, Logrudp, "rudp: kick\n");
355         bp = qget(c->wq);
356         if(bp == nil)
357                 return;
358
359         ucb = (Rudpcb*)c->ptcl;
360         switch(ucb->headers) {
361         case 7:
362                 /* get user specified addresses */
363                 bp = pullupblock(bp, UDP_USEAD7);
364                 if(bp == nil)
365                         return;
366                 ipmove(raddr, bp->rp);
367                 bp->rp += IPaddrlen;
368                 ipmove(laddr, bp->rp);
369                 bp->rp += IPaddrlen;
370                 /* pick interface closest to dest */
371                 if(ipforme(f, laddr) != Runi)
372                         findlocalip(f, laddr, raddr);
373                 bp->rp += IPaddrlen;            /* Ignore ifc address */
374                 rport = nhgets(bp->rp);
375                 bp->rp += 2+2;                  /* Ignore local port */
376                 break;
377         case 6:
378                 /* get user specified addresses */
379                 bp = pullupblock(bp, UDP_USEAD6);
380                 if(bp == nil)
381                         return;
382                 ipmove(raddr, bp->rp);
383                 bp->rp += IPaddrlen;
384                 ipmove(laddr, bp->rp);
385                 bp->rp += IPaddrlen;
386                 /* pick interface closest to dest */
387                 if(ipforme(f, laddr) != Runi)
388                         findlocalip(f, laddr, raddr);
389                 rport = nhgets(bp->rp);
390
391                 bp->rp += 4;                    /* Igonore local port */
392                 break;
393         default:
394                 ipmove(raddr, c->raddr);
395                 ipmove(laddr, c->laddr);
396                 rport = c->rport;
397
398                 break;
399         }
400
401         dlen = blocklen(bp);
402
403         /* Make space to fit rudp & ip header */
404         bp = padblock(bp, UDP_IPHDR+UDP_RHDRSIZE);
405         if(bp == nil)
406                 return;
407
408         uh = (Udphdr *)(bp->rp);
409         uh->vihl = IP_VER4;
410
411         rh = (Rudphdr*)uh;
412
413         ptcllen = dlen + (UDP_RHDRSIZE-UDP_PHDRSIZE);
414         uh->Unused = 0;
415         uh->udpproto = IP_UDPPROTO;
416         uh->frag[0] = 0;
417         uh->frag[1] = 0;
418         hnputs(uh->udpplen, ptcllen);
419         switch(ucb->headers){
420         case 6:
421         case 7:
422                 v6tov4(uh->udpdst, raddr);
423                 hnputs(uh->udpdport, rport);
424                 v6tov4(uh->udpsrc, laddr);
425                 break;
426         default:
427                 v6tov4(uh->udpdst, c->raddr);
428                 hnputs(uh->udpdport, c->rport);
429                 if(ipcmp(c->laddr, IPnoaddr) == 0)
430                         findlocalip(f, c->laddr, c->raddr);
431                 v6tov4(uh->udpsrc, c->laddr);
432                 break;
433         }
434         hnputs(uh->udpsport, c->lport);
435         hnputs(uh->udplen, ptcllen);
436         uh->udpcksum[0] = 0;
437         uh->udpcksum[1] = 0;
438
439         qlock(ucb);
440         r = relstate(ucb, raddr, rport, "kick");
441         r->sndseq = NEXTSEQ(r->sndseq);
442         hnputl(rh->relseq, r->sndseq);
443         hnputl(rh->relsgen, r->sndgen);
444
445         hnputl(rh->relack, r->rcvseq);  /* ACK last rcvd packet */
446         hnputl(rh->relagen, r->rcvgen);
447
448         if(r->rcvseq != r->acksent)
449                 r->acksent = r->rcvseq;
450
451         hnputs(uh->udpcksum, ptclcsum(bp, UDP_IPHDR, dlen+UDP_RHDRSIZE));
452
453         relackq(r, bp);
454         qunlock(ucb);
455
456         upriv->ustats.rudpOutDatagrams++;
457
458         DPRINT("sent: %lud/%lud, %lud/%lud\n", 
459                 r->sndseq, r->sndgen, r->rcvseq, r->rcvgen);
460
461         doipoput(c, f, bp, 0, c->ttl, c->tos);
462
463         if(waserror()) {
464                 relput(r);
465                 qunlock(&r->lock);
466                 nexterror();
467         }
468
469         /* flow control of sorts */
470         qlock(&r->lock);
471         if(UNACKED(r) > Maxunacked){
472                 r->blocked = 1;
473                 sleep(&r->vous, flow, r);
474                 r->blocked = 0;
475         }
476
477         qunlock(&r->lock);
478         relput(r);
479         poperror();
480 }
481
482 void
483 rudpiput(Proto *rudp, Ipifc *ifc, Block *bp)
484 {
485         int len, olen, ottl;
486         Udphdr *uh;
487         Conv *c;
488         Rudpcb *ucb;
489         uchar raddr[IPaddrlen], laddr[IPaddrlen];
490         ushort rport, lport;
491         Rudppriv *upriv;
492         Fs *f;
493         uchar *p;
494
495         upriv = rudp->priv;
496         f = rudp->f;
497
498         upriv->ustats.rudpInDatagrams++;
499
500         uh = (Udphdr*)(bp->rp);
501
502         /* Put back pseudo header for checksum 
503          * (remember old values for icmpnoconv()) 
504          */
505         ottl = uh->Unused;
506         uh->Unused = 0;
507         len = nhgets(uh->udplen);
508         olen = nhgets(uh->udpplen);
509         hnputs(uh->udpplen, len);
510
511         v4tov6(raddr, uh->udpsrc);
512         v4tov6(laddr, uh->udpdst);
513         lport = nhgets(uh->udpdport);
514         rport = nhgets(uh->udpsport);
515
516         if(nhgets(uh->udpcksum)) {
517                 if(ptclcsum(bp, UDP_IPHDR, len+UDP_PHDRSIZE)) {
518                         upriv->ustats.rudpInErrors++;
519                         upriv->csumerr++;
520                         netlog(f, Logrudp, "rudp: checksum error %I\n", raddr);
521                         DPRINT("rudp: checksum error %I\n", raddr);
522                         freeblist(bp);
523                         return;
524                 }
525         }
526
527         qlock(rudp);
528
529         c = iphtlook(&upriv->ht, raddr, rport, laddr, lport);
530         if(c == nil){
531                 /* no converstation found */
532                 upriv->ustats.rudpNoPorts++;
533                 qunlock(rudp);
534                 netlog(f, Logudp, "udp: no conv %I!%d -> %I!%d\n", raddr, rport,
535                         laddr, lport);
536                 uh->Unused = ottl;
537                 hnputs(uh->udpplen, olen);
538                 icmpnoconv(f, bp);
539                 freeblist(bp);
540                 return;
541         }
542         ucb = (Rudpcb*)c->ptcl;
543         qlock(ucb);
544         qunlock(rudp);
545
546         if(reliput(c, bp, raddr, rport) < 0){
547                 qunlock(ucb);
548                 freeb(bp);
549                 return;
550         }
551
552         /*
553          * Trim the packet down to data size
554          */
555
556         len -= (UDP_RHDRSIZE-UDP_PHDRSIZE);
557         bp = trimblock(bp, UDP_IPHDR+UDP_RHDRSIZE, len);
558         if(bp == nil) {
559                 netlog(f, Logrudp, "rudp: len err %I.%d -> %I.%d\n", 
560                         raddr, rport, laddr, lport);
561                 DPRINT("rudp: len err %I.%d -> %I.%d\n", 
562                         raddr, rport, laddr, lport);
563                 upriv->lenerr++;
564                 return;
565         }
566
567         netlog(f, Logrudpmsg, "rudp: %I.%d -> %I.%d l %d\n", 
568                 raddr, rport, laddr, lport, len);
569
570         switch(ucb->headers){
571         case 7:
572                 /* pass the src address */
573                 bp = padblock(bp, UDP_USEAD7);
574                 p = bp->rp;
575                 ipmove(p, raddr); p += IPaddrlen;
576                 ipmove(p, laddr); p += IPaddrlen;
577                 ipmove(p, ifc->lifc->local); p += IPaddrlen;
578                 hnputs(p, rport); p += 2;
579                 hnputs(p, lport);
580                 break;
581         case 6:
582                 /* pass the src address */
583                 bp = padblock(bp, UDP_USEAD6);
584                 p = bp->rp;
585                 ipmove(p, raddr); p += IPaddrlen;
586                 ipmove(p, ipforme(f, laddr)==Runi ? laddr : ifc->lifc->local); p += IPaddrlen;
587                 hnputs(p, rport); p += 2;
588                 hnputs(p, lport);
589                 break;
590         default:
591                 /* connection oriented rudp */
592                 if(ipcmp(c->raddr, IPnoaddr) == 0){
593                         /* save the src address in the conversation */
594                         ipmove(c->raddr, raddr);
595                         c->rport = rport;
596
597                         /* reply with the same ip address (if not broadcast) */
598                         if(ipforme(f, laddr) == Runi)
599                                 ipmove(c->laddr, laddr);
600                         else
601                                 v4tov6(c->laddr, ifc->lifc->local);
602                 }
603                 break;
604         }
605         if(bp->next)
606                 bp = concatblock(bp);
607
608         if(qfull(c->rq)) {
609                 netlog(f, Logrudp, "rudp: qfull %I.%d -> %I.%d\n", raddr, rport,
610                         laddr, lport);
611                 freeblist(bp);
612         }
613         else
614                 qpass(c->rq, bp);
615         
616         qunlock(ucb);
617 }
618
619 static char *rudpunknown = "unknown rudp ctl request";
620
621 char*
622 rudpctl(Conv *c, char **f, int n)
623 {
624         Rudpcb *ucb;
625         uchar ip[IPaddrlen];
626         int x;
627
628         ucb = (Rudpcb*)c->ptcl;
629         if(n < 1)
630                 return rudpunknown;
631
632         if(strcmp(f[0], "headers++4") == 0){
633                 ucb->headers = 7;
634                 return nil;
635         } else if(strcmp(f[0], "headers") == 0){
636                 ucb->headers = 6;
637                 return nil;
638         } else if(strcmp(f[0], "hangup") == 0){
639                 if(n < 3)
640                         return "bad syntax";
641                 parseip(ip, f[1]);
642                 x = atoi(f[2]);
643                 qlock(ucb);
644                 relforget(c, ip, x, 1);
645                 qunlock(ucb);
646                 return nil;
647         } else if(strcmp(f[0], "randdrop") == 0){
648                 x = 10;         /* default is 10% */
649                 if(n > 1)
650                         x = atoi(f[1]);
651                 if(x > 100 || x < 0)
652                         return "illegal rudp drop rate";
653                 ucb->randdrop = x;
654                 return nil;
655         }
656         return rudpunknown;
657 }
658
659 void
660 rudpadvise(Proto *rudp, Block *bp, char *msg)
661 {
662         Udphdr *h;
663         uchar source[IPaddrlen], dest[IPaddrlen];
664         ushort psource, pdest;
665         Conv *s, **p;
666
667         h = (Udphdr*)(bp->rp);
668
669         v4tov6(dest, h->udpdst);
670         v4tov6(source, h->udpsrc);
671         psource = nhgets(h->udpsport);
672         pdest = nhgets(h->udpdport);
673
674         /* Look for a connection */
675         for(p = rudp->conv; *p; p++) {
676                 s = *p;
677                 if(s->rport == pdest)
678                 if(s->lport == psource)
679                 if(ipcmp(s->raddr, dest) == 0)
680                 if(ipcmp(s->laddr, source) == 0){
681                         qhangup(s->rq, msg);
682                         qhangup(s->wq, msg);
683                         break;
684                 }
685         }
686         freeblist(bp);
687 }
688
689 int
690 rudpstats(Proto *rudp, char *buf, int len)
691 {
692         Rudppriv *upriv;
693
694         upriv = rudp->priv;
695         return snprint(buf, len, "%lud %lud %lud %lud %lud %lud\n",
696                 upriv->ustats.rudpInDatagrams,
697                 upriv->ustats.rudpNoPorts,
698                 upriv->ustats.rudpInErrors,
699                 upriv->ustats.rudpOutDatagrams,
700                 upriv->rxmits,
701                 upriv->orders);
702 }
703
704 void
705 rudpinit(Fs *fs)
706 {
707
708         Proto *rudp;
709
710         rudp = smalloc(sizeof(Proto));
711         rudp->priv = smalloc(sizeof(Rudppriv));
712         rudp->name = "rudp";
713         rudp->connect = rudpconnect;
714         rudp->announce = rudpannounce;
715         rudp->ctl = rudpctl;
716         rudp->state = rudpstate;
717         rudp->create = rudpcreate;
718         rudp->close = rudpclose;
719         rudp->rcv = rudpiput;
720         rudp->advise = rudpadvise;
721         rudp->stats = rudpstats;
722         rudp->ipproto = IP_UDPPROTO;
723         rudp->nc = 16;
724         rudp->ptclsize = sizeof(Rudpcb);
725
726         Fsproto(fs, rudp);
727 }
728
729 /*********************************************/
730 /* Here starts the reliable helper functions */
731 /*********************************************/
732 /*
733  *  Enqueue a copy of an unacked block for possible retransmissions
734  */
735 void
736 relackq(Reliable *r, Block *bp)
737 {
738         Block *np;
739
740         np = copyblock(bp, blocklen(bp));
741         if(r->unacked)
742                 r->unackedtail->list = np;
743         else {
744                 /* restart timer */
745                 r->timeout = 0;
746                 r->xmits = 1;
747                 r->unacked = np;
748         }
749         r->unackedtail = np;
750         np->list = nil;
751 }
752
753 /*
754  *  retransmit unacked blocks
755  */
756 void
757 relackproc(void *a)
758 {
759         Rudpcb *ucb;
760         Proto *rudp;
761         Reliable *r;
762         Conv **s, *c;
763
764         rudp = (Proto *)a;
765
766 loop:
767         tsleep(&up->sleep, return0, 0, Rudptickms);
768
769         for(s = rudp->conv; *s; s++) {
770                 c = *s;
771                 ucb = (Rudpcb*)c->ptcl;
772                 qlock(ucb);
773
774                 for(r = ucb->r; r; r = r->next) {
775                         if(r->unacked != nil){
776                                 r->timeout += Rudptickms;
777                                 if(r->timeout > Rudprxms*r->xmits)
778                                         relrexmit(c, r);
779                         }
780                         if(r->acksent != r->rcvseq)
781                                 relsendack(c, r, 0);
782                 }
783                 qunlock(ucb);
784         }
785         goto loop;
786 }
787
788 /*
789  *  get the state record for a conversation
790  */
791 Reliable*
792 relstate(Rudpcb *ucb, uchar *addr, ushort port, char *from)
793 {
794         Reliable *r, **l;
795
796         l = &ucb->r;
797         for(r = *l; r; r = *l){
798                 if(memcmp(addr, r->addr, IPaddrlen) == 0 && 
799                     port == r->port)
800                         break;
801                 l = &r->next;
802         }
803
804         /* no state for this addr/port, create some */
805         if(r == nil){
806                 while(generation == 0)
807                         generation = rand();
808
809                 DPRINT("from %s new state %lud for %I!%ud\n", 
810                         from, generation, addr, port);
811
812                 r = smalloc(sizeof(Reliable));
813                 memmove(r->addr, addr, IPaddrlen);
814                 r->port = port;
815                 r->unacked = 0;
816                 if(generation == Hangupgen)
817                         generation++;
818                 r->sndgen = generation++;
819                 r->sndseq = 0;
820                 r->ackrcvd = 0;
821                 r->rcvgen = 0;
822                 r->rcvseq = 0;
823                 r->acksent = 0;
824                 r->xmits = 0;
825                 r->timeout = 0;
826                 r->ref = 0;
827                 incref(r);      /* one reference for being in the list */
828
829                 *l = r;
830         }
831
832         incref(r);
833         return r;
834 }
835
836 void
837 relput(Reliable *r)
838 {
839         if(decref(r) == 0)
840                 free(r);
841 }
842
843 /*
844  *  forget a Reliable state
845  */
846 void
847 relforget(Conv *c, uchar *ip, int port, int originator)
848 {
849         Rudpcb *ucb;
850         Reliable *r, **l;
851
852         ucb = (Rudpcb*)c->ptcl;
853
854         l = &ucb->r;
855         for(r = *l; r; r = *l){
856                 if(ipcmp(ip, r->addr) == 0 && port == r->port){
857                         *l = r->next;
858                         if(originator)
859                                 relsendack(c, r, 1);
860                         relhangup(c, r);
861                         relput(r);      /* remove from the list */
862                         break;
863                 }
864                 l = &r->next;
865         }
866 }
867
868 /* 
869  *  process a rcvd reliable packet. return -1 if not to be passed to user process,
870  *  0 therwise.
871  *
872  *  called with ucb locked.
873  */
874 int
875 reliput(Conv *c, Block *bp, uchar *addr, ushort port)
876 {
877         Block *nbp;
878         Rudpcb *ucb;
879         Rudppriv *upriv;
880         Udphdr *uh;
881         Reliable *r;
882         Rudphdr *rh;
883         ulong seq, ack, sgen, agen, ackreal;
884         int rv = -1;
885
886         /* get fields */
887         uh = (Udphdr*)(bp->rp);
888         rh = (Rudphdr*)uh;
889         seq = nhgetl(rh->relseq);
890         sgen = nhgetl(rh->relsgen);
891         ack = nhgetl(rh->relack);
892         agen = nhgetl(rh->relagen);
893
894         upriv = c->p->priv;
895         ucb = (Rudpcb*)c->ptcl;
896         r = relstate(ucb, addr, port, "input");
897
898         DPRINT("rcvd %lud/%lud, %lud/%lud, r->sndgen = %lud\n", 
899                 seq, sgen, ack, agen, r->sndgen);
900
901         /* if acking an incorrect generation, ignore */
902         if(ack && agen != r->sndgen)
903                 goto out;
904
905         /* Look for a hangup */
906         if(sgen == Hangupgen) {
907                 if(agen == r->sndgen)
908                         relforget(c, addr, port, 0);
909                 goto out;
910         }
911
912         /* make sure we're not talking to a new remote side */
913         if(r->rcvgen != sgen){
914                 if(seq != 0 && seq != 1)
915                         goto out;
916
917                 /* new connection */
918                 if(r->rcvgen != 0){
919                         DPRINT("new con r->rcvgen = %lud, sgen = %lud\n", r->rcvgen, sgen);
920                         relhangup(c, r);
921                 }
922                 r->rcvgen = sgen;
923         }
924
925         /* dequeue acked packets */
926         if(ack && agen == r->sndgen){
927                 ackreal = 0;
928                 while(r->unacked != nil && INSEQ(ack, r->ackrcvd, r->sndseq)){
929                         nbp = r->unacked;
930                         r->unacked = nbp->list;
931                         DPRINT("%lud/%lud acked, r->sndgen = %lud\n", 
932                                ack, agen, r->sndgen);
933                         freeb(nbp);
934                         r->ackrcvd = NEXTSEQ(r->ackrcvd);
935                         ackreal = 1;
936                 }
937
938                 /* flow control */
939                 if(UNACKED(r) < Maxunacked/8 && r->blocked)
940                         wakeup(&r->vous);
941
942                 /*
943                  *  retransmit next packet if the acked packet
944                  *  was transmitted more than once
945                  */
946                 if(ackreal && r->unacked != nil){
947                         r->timeout = 0;
948                         if(r->xmits > 1){
949                                 r->xmits = 1;
950                                 relrexmit(c, r);
951                         }
952                 }
953                 
954         }
955
956         /* no message or input queue full */
957         if(seq == 0 || qfull(c->rq))
958                 goto out;
959
960         /* refuse out of order delivery */
961         if(seq != NEXTSEQ(r->rcvseq)){
962                 relsendack(c, r, 0);    /* tell him we got it already */
963                 upriv->orders++;
964                 DPRINT("out of sequence %lud not %lud\n", seq, NEXTSEQ(r->rcvseq));
965                 goto out;
966         }
967         r->rcvseq = seq;
968
969         rv = 0;
970 out:
971         relput(r);
972         return rv;
973 }
974
975 void
976 relsendack(Conv *c, Reliable *r, int hangup)
977 {
978         Udphdr *uh;
979         Block *bp;
980         Rudphdr *rh;
981         int ptcllen;
982         Fs *f;
983
984         bp = allocb(UDP_IPHDR + UDP_RHDRSIZE);
985         if(bp == nil)
986                 return;
987         bp->wp += UDP_IPHDR + UDP_RHDRSIZE;
988         f = c->p->f;
989         uh = (Udphdr *)(bp->rp);
990         uh->vihl = IP_VER4;
991         rh = (Rudphdr*)uh;
992
993         ptcllen = (UDP_RHDRSIZE-UDP_PHDRSIZE);
994         uh->Unused = 0;
995         uh->udpproto = IP_UDPPROTO;
996         uh->frag[0] = 0;
997         uh->frag[1] = 0;
998         hnputs(uh->udpplen, ptcllen);
999
1000         v6tov4(uh->udpdst, r->addr);
1001         hnputs(uh->udpdport, r->port);
1002         hnputs(uh->udpsport, c->lport);
1003         if(ipcmp(c->laddr, IPnoaddr) == 0)
1004                 findlocalip(f, c->laddr, c->raddr);
1005         v6tov4(uh->udpsrc, c->laddr);
1006         hnputs(uh->udplen, ptcllen);
1007
1008         if(hangup)
1009                 hnputl(rh->relsgen, Hangupgen);
1010         else
1011                 hnputl(rh->relsgen, r->sndgen);
1012         hnputl(rh->relseq, 0);
1013         hnputl(rh->relagen, r->rcvgen);
1014         hnputl(rh->relack, r->rcvseq);
1015
1016         if(r->acksent < r->rcvseq)
1017                 r->acksent = r->rcvseq;
1018
1019         uh->udpcksum[0] = 0;
1020         uh->udpcksum[1] = 0;
1021         hnputs(uh->udpcksum, ptclcsum(bp, UDP_IPHDR, UDP_RHDRSIZE));
1022
1023         DPRINT("sendack: %lud/%lud, %lud/%lud\n", 0L, r->sndgen, r->rcvseq, r->rcvgen);
1024         doipoput(c, f, bp, 0, c->ttl, c->tos);
1025 }
1026
1027
1028 /*
1029  *  called with ucb locked (and c locked if user initiated close)
1030  */
1031 void
1032 relhangup(Conv *c, Reliable *r)
1033 {
1034         int n;
1035         Block *bp;
1036         char hup[ERRMAX];
1037
1038         n = snprint(hup, sizeof(hup), "hangup %I!%d", r->addr, r->port);
1039         qproduce(c->eq, hup, n);
1040
1041         /*
1042          *  dump any unacked outgoing messages
1043          */
1044         for(bp = r->unacked; bp != nil; bp = r->unacked){
1045                 r->unacked = bp->list;
1046                 bp->list = nil;
1047                 freeb(bp);
1048         }
1049
1050         r->rcvgen = 0;
1051         r->rcvseq = 0;
1052         r->acksent = 0;
1053         if(generation == Hangupgen)
1054                 generation++;
1055         r->sndgen = generation++;
1056         r->sndseq = 0;
1057         r->ackrcvd = 0;
1058         r->xmits = 0;
1059         r->timeout = 0;
1060         wakeup(&r->vous);
1061 }
1062
1063 /*
1064  *  called with ucb locked
1065  */
1066 void
1067 relrexmit(Conv *c, Reliable *r)
1068 {
1069         Rudppriv *upriv;
1070         Block *np;
1071         Fs *f;
1072
1073         upriv = c->p->priv;
1074         f = c->p->f;
1075         r->timeout = 0;
1076         if(r->xmits++ > Rudpmaxxmit){
1077                 relhangup(c, r);
1078                 return;
1079         }
1080
1081         upriv->rxmits++;
1082         np = copyblock(r->unacked, blocklen(r->unacked));
1083         DPRINT("rxmit r->ackrvcd+1 = %lud\n", r->ackrcvd+1);
1084         doipoput(c, f, np, 0, c->ttl, c->tos);
1085 }