|
4
|
1 /*--------------------------------------------------------------------------
|
|
|
2 NETREK II -- Paradise
|
|
|
3
|
|
|
4 Permission to use, copy, modify, and distribute this software and its
|
|
|
5 documentation, or any derivative works thereof, for any NON-COMMERCIAL
|
|
|
6 purpose and without fee is hereby granted, provided that this copyright
|
|
|
7 notice appear in all copies. No representations are made about the
|
|
|
8 suitability of this software for any purpose. This software is provided
|
|
|
9 "as is" without express or implied warranty.
|
|
|
10
|
|
|
11 Xtrek Copyright 1986 Chris Guthrie
|
|
|
12 Netrek (Xtrek II) Copyright 1989 Kevin P. Smith
|
|
|
13 Scott Silvey
|
|
|
14 Paradise II (Netrek II) Copyright 1993 Larry Denys
|
|
|
15 Kurt Olsen
|
|
|
16 Brandon Gillespie
|
|
|
17 --------------------------------------------------------------------------*/
|
|
|
18
|
|
|
19 #include "config.h"
|
|
|
20 #include <stdio.h>
|
|
|
21 #include <signal.h>
|
|
|
22 #include <sys/types.h>
|
|
|
23 #include <sys/time.h>
|
|
|
24 #include <math.h>
|
|
|
25 #include <errno.h>
|
|
|
26 #include <netinet/in.h>
|
|
|
27 #include "defs.h"
|
|
|
28 #include "struct.h"
|
|
|
29 #include "data.h"
|
|
|
30 #include "packets.h"
|
|
|
31 #include "shmem.h"
|
|
|
32
|
|
|
33 #define PING_DEBUG 0 /* debugging */
|
|
|
34
|
|
|
35 /* special fields in stats record for rountrip delay and packet loss */
|
|
|
36 #define INL_STATS
|
|
|
37
|
|
|
38
|
|
|
39 static unsigned char ping_id; /* wraparound expected */
|
|
|
40 static int ping_lag; /* ping roundtrip delay */
|
|
|
41
|
|
|
42 static int tloss_sc, /* total packet loss s-c */
|
|
|
43 tloss_cs, /* total packet loss c-s */
|
|
|
44 iloss_sc, /* inc. packet loss s-c */
|
|
|
45 iloss_cs; /* inc. packet loss c-s */
|
|
|
46
|
|
|
47 /*
|
|
|
48 * This structure allows us to send several pings before any response is
|
|
|
49 * received without losing information -- as would be the case for roundtrip
|
|
|
50 * times equal to or larger then the ping interval times. HASHSIZE * ping
|
|
|
51 * interval must be greater then the largest expected roundtrip time.
|
|
|
52 */
|
|
|
53
|
|
|
54 #define HASHSIZE 32
|
|
|
55 #define PITH(i) (((int)i) & (HASHSIZE-1))
|
|
|
56
|
|
|
57 static
|
|
|
58 struct
|
|
|
59 {
|
|
|
60 long time;
|
|
|
61 long packets_sent_at_ping;
|
|
|
62 } ping_sent[HASHSIZE];
|
|
|
63
|
|
|
64
|
|
|
65 void calc_loss();
|
|
|
66 void update_lag_stats();
|
|
|
67 void update_loss_stats();
|
|
|
68 int mstime();
|
|
|
69 int msetime();
|
|
|
70
|
|
|
71 /*
|
|
|
72 * response from client
|
|
|
73 */
|
|
|
74
|
|
|
75 void
|
|
|
76 pingResponse(packet)
|
|
|
77 struct ping_cpacket *packet;
|
|
|
78 {
|
|
|
79 register i;
|
|
|
80 static int last_num;
|
|
|
81
|
|
|
82 if (!ping || packet->pingme != 1)
|
|
|
83 return; /* oops, garbage */
|
|
|
84
|
|
|
85 ping_ghostbust = 0; /* don't ghostbust, client is alive */
|
|
|
86
|
|
|
87 /* throw out out-of-order packets */
|
|
|
88 i = uchar_diff((int) packet->number, last_num);
|
|
|
89 if (i < 0)
|
|
|
90 {
|
|
|
91 #if PING_DEBUG >= 1
|
|
|
92 fprintf(stderr, "out-of-order response ignored: %d (last: %d)\n",
|
|
|
93 packet->number, last_num);
|
|
|
94 fflush(stderr);
|
|
|
95 #endif
|
|
|
96 return;
|
|
|
97 }
|
|
|
98 last_num = packet->number;
|
|
|
99 i = PITH(last_num);
|
|
|
100
|
|
|
101 /* calculate roundtrip */
|
|
|
102 ping_lag = mstime() - ping_sent[i].time;
|
|
|
103
|
|
|
104 #ifdef INL_STATS
|
|
|
105 /* fill in lag stats fields */
|
|
|
106 update_lag_stats();
|
|
|
107 #endif
|
|
|
108
|
|
|
109 /* watch out for div by 0 */
|
|
|
110 if (!packets_received || !ping_sent[i].packets_sent_at_ping)
|
|
|
111 return;
|
|
|
112
|
|
|
113 /* calculate total packet loss */
|
|
|
114 calc_loss(i, packet);
|
|
|
115
|
|
|
116 #ifdef INL_STATS
|
|
|
117 update_loss_stats();
|
|
|
118 #endif
|
|
|
119 }
|
|
|
120
|
|
|
121 /*
|
|
|
122 * request from server
|
|
|
123 */
|
|
|
124
|
|
|
125 void
|
|
|
126 sendClientPing()
|
|
|
127 {
|
|
|
128 struct ping_spacket packet;
|
|
|
129
|
|
|
130 ping_ghostbust++;
|
|
|
131 ping_id++; /* ok to wrap */
|
|
|
132
|
|
|
133 packet.type = SP_PING;
|
|
|
134 packet.number = (unsigned char) ping_id;
|
|
|
135 packet.lag = htons((unsigned short) ping_lag);
|
|
|
136 packet.tloss_sc = tloss_sc;
|
|
|
137 packet.tloss_cs = tloss_cs;
|
|
|
138 packet.iloss_sc = iloss_sc;
|
|
|
139 packet.iloss_cs = iloss_cs;
|
|
|
140
|
|
|
141 ping_sent[PITH(ping_id)].time = mstime();
|
|
|
142 /*
|
|
|
143 * printf("ping sent at %d\n", msetime());
|
|
|
144 */
|
|
|
145
|
|
|
146 sendClientPacket(&packet);
|
|
|
147
|
|
|
148 ping_sent[PITH(ping_id)].packets_sent_at_ping = packets_sent;
|
|
|
149 }
|
|
|
150
|
|
|
151 void
|
|
|
152 calc_loss(i, packet)
|
|
|
153 int i;
|
|
|
154 struct ping_cpacket *packet;
|
|
|
155 {
|
|
|
156 /* tloss vars */
|
|
|
157 register cp_recv, /* client packets recv */
|
|
|
158 cp_sent; /* client packets sent */
|
|
|
159 int s_to_c_dropped, /* server to client */
|
|
|
160 c_to_s_dropped; /* client to server */
|
|
|
161 static int old_s_to_c_dropped,/* previous update */
|
|
|
162 old_c_to_s_dropped; /* "" */
|
|
|
163 /* iloss vars */
|
|
|
164 int p_sent, p_recv;
|
|
|
165
|
|
|
166 static
|
|
|
167 int timer;
|
|
|
168
|
|
|
169 static int inc_packets_sent, /* packets sent start-point */
|
|
|
170 inc_packets_received, /* packets recvd start-pt */
|
|
|
171 inc_s_to_c_dropped, /* dropped s-to-c start-pt */
|
|
|
172 inc_c_to_s_dropped; /* dropped c-to-s start-pt */
|
|
|
173
|
|
|
174 if (!timer)
|
|
|
175 timer = configvals->ping_iloss_interval;
|
|
|
176
|
|
|
177 cp_recv = ntohl(packet->cp_recv);
|
|
|
178 cp_sent = ntohl(packet->cp_sent);
|
|
|
179
|
|
|
180 /* at ping time, total packets dropped from server to client */
|
|
|
181 s_to_c_dropped = ping_sent[i].packets_sent_at_ping - cp_recv;
|
|
|
182
|
|
|
183 if (s_to_c_dropped < old_s_to_c_dropped)
|
|
|
184 {
|
|
|
185 /*
|
|
|
186 * The network may duplicate or send out-of-order packets. Both are
|
|
|
187 * detected and thrown out by the client if sequence checking is on. If
|
|
|
188 * not there's not much we can do -- there's no way to distinguish a
|
|
|
189 * duplicated packet from a series of out of order packets. While the
|
|
|
190 * latter case cancels itself out eventually in terms of packet loss, the
|
|
|
191 * former hides real packet loss by adding extra packets. We'll have to
|
|
|
192 * kludge it by adding the extra packets the client thinks it got to
|
|
|
193 * packets_sent
|
|
|
194 */
|
|
|
195 packets_sent += old_s_to_c_dropped - s_to_c_dropped;
|
|
|
196 /* and adjust s_to_c_dropped so we don't get a negative packet loss */
|
|
|
197 s_to_c_dropped = old_s_to_c_dropped;
|
|
|
198 }
|
|
|
199
|
|
|
200 /* total loss server-to-client since start of connection */
|
|
|
201 tloss_sc = 100 -
|
|
|
202 (100 * (ping_sent[i].packets_sent_at_ping - s_to_c_dropped)) /
|
|
|
203 ping_sent[i].packets_sent_at_ping;
|
|
|
204
|
|
|
205 /*
|
|
|
206 * at ping time, total packets dropped from client to server NOTE: not
|
|
|
207 * packets_received_at_ping since the client may have sent any amount of
|
|
|
208 * packets between the time we sent the ping and the time the client
|
|
|
209 * received it.
|
|
|
210 */
|
|
|
211 c_to_s_dropped = cp_sent - packets_received;
|
|
|
212
|
|
|
213 #if PING_DEBUG >= 2
|
|
|
214 printf("cp_sent: %d, packets_received: %d\n",
|
|
|
215 cp_sent, packets_received);
|
|
|
216 #endif
|
|
|
217
|
|
|
218 if (c_to_s_dropped < old_c_to_s_dropped)
|
|
|
219 {
|
|
|
220 /*
|
|
|
221 * The network may duplicate or send out-of-order packets. Since no
|
|
|
222 * sequence checking is done by the server, there's not much we can do --
|
|
|
223 * there's no way to distinguish a duplicated packet from a series of out
|
|
|
224 * of order packets. While the latter case cancels itself out eventually
|
|
|
225 * in terms of packet loss, the former hides real packet loss by adding
|
|
|
226 * extra packets. We'll have to kludge it by subtracting the extra
|
|
|
227 * packets we think we got from the client from packets_received.
|
|
|
228 */
|
|
|
229 packets_received -= old_c_to_s_dropped - c_to_s_dropped;
|
|
|
230 /* and adjust c_to_s_dropped so we don't get a negative packet loss */
|
|
|
231 c_to_s_dropped = old_c_to_s_dropped;
|
|
|
232 }
|
|
|
233
|
|
|
234 /* total loss client-to-server since start of connection */
|
|
|
235 tloss_cs = 100 -
|
|
|
236 (100 * (packets_received - c_to_s_dropped)) / (packets_received ? packets_received : 1);
|
|
|
237
|
|
|
238 old_s_to_c_dropped = s_to_c_dropped;
|
|
|
239 old_c_to_s_dropped = c_to_s_dropped;
|
|
|
240
|
|
|
241 /* Incremental packet loss */
|
|
|
242
|
|
|
243 /* packets sent since last ping response */
|
|
|
244 p_sent = ping_sent[i].packets_sent_at_ping - inc_packets_sent;
|
|
|
245
|
|
|
246 /* packets received since last ping response */
|
|
|
247 p_recv = packets_received - inc_packets_received;
|
|
|
248
|
|
|
249 if (!p_sent || !p_recv)
|
|
|
250 {
|
|
|
251 /* just in case */
|
|
|
252 return;
|
|
|
253 }
|
|
|
254
|
|
|
255 /* percent loss server-to-client since PACKET_LOSS_INTERVAL */
|
|
|
256 iloss_sc = 100 -
|
|
|
257 (100 * (p_sent - (s_to_c_dropped - inc_s_to_c_dropped))) / p_sent;
|
|
|
258 /*
|
|
|
259 * we're not going to do any of the adjustments we did in tloss
|
|
|
260 * calculations since this starts fresh every PACKET_LOSS_INTERVAL
|
|
|
261 */
|
|
|
262 if (iloss_sc < 0)
|
|
|
263 iloss_sc = 0;
|
|
|
264
|
|
|
265 /* total percent loss client-to-server since PACKET_LOSS_INTERVAL */
|
|
|
266 iloss_cs = 100 -
|
|
|
267 (100 * (p_recv - (c_to_s_dropped - inc_c_to_s_dropped))) / p_recv;
|
|
|
268 /*
|
|
|
269 * we're not going to do any of the adjustments we did in tloss
|
|
|
270 * calculations since this starts fresh every PACKET_LOSS_INTERVAL
|
|
|
271 */
|
|
|
272 if (iloss_cs < 0)
|
|
|
273 iloss_cs = 0;
|
|
|
274
|
|
|
275 /*
|
|
|
276 * we update these variables every PACKET_LOSS_INTERVAL seconds to start a
|
|
|
277 * fresh increment
|
|
|
278 */
|
|
|
279 if ((timer % configvals->ping_iloss_interval) == 0)
|
|
|
280 {
|
|
|
281 inc_s_to_c_dropped = s_to_c_dropped;
|
|
|
282 inc_c_to_s_dropped = c_to_s_dropped;
|
|
|
283
|
|
|
284 inc_packets_sent = ping_sent[i].packets_sent_at_ping;
|
|
|
285 inc_packets_received = packets_received;
|
|
|
286 }
|
|
|
287
|
|
|
288 timer++;
|
|
|
289 }
|
|
|
290
|
|
|
291 #ifdef INL_STATS
|
|
|
292
|
|
|
293 /*
|
|
|
294 * Lag stats struct player .p_avrt - average round trip time ms struct
|
|
|
295 * player .p_stdv - standard deviation in rt time struct player .p_pkls -
|
|
|
296 * input/output packet loss
|
|
|
297 */
|
|
|
298
|
|
|
299 static int sum, n, s2;
|
|
|
300 static int M, var;
|
|
|
301
|
|
|
302 void
|
|
|
303 update_lag_stats()
|
|
|
304 {
|
|
|
305 n++;
|
|
|
306 sum += ping_lag;
|
|
|
307 s2 += (ping_lag * ping_lag);
|
|
|
308 if (n == 1)
|
|
|
309 return;
|
|
|
310
|
|
|
311 M = sum / n;
|
|
|
312 var = (s2 - M * sum) / (n - 1);
|
|
|
313
|
|
|
314 /* average round trip time */
|
|
|
315 me->p_avrt = M;
|
|
|
316 /* standard deviation */
|
|
|
317 if (var > 0)
|
|
|
318 me->p_stdv = (int) isqrt(var);
|
|
|
319 }
|
|
|
320
|
|
|
321 void
|
|
|
322 update_loss_stats()
|
|
|
323 {
|
|
|
324 /*
|
|
|
325 * packet loss (as average of server-to-client, client-to-server loss),
|
|
|
326 * give tloss_sc extra weight (or should we?)
|
|
|
327 */
|
|
|
328 me->p_pkls = (2 * tloss_sc + tloss_cs) / 3;
|
|
|
329 }
|
|
|
330 #endif /* INL_STATS */
|
|
|
331
|
|
|
332 /* utilities */
|
|
|
333
|
|
|
334 /* ms time from start */
|
|
|
335 int
|
|
|
336 mstime()
|
|
|
337 {
|
|
|
338 static struct timeval tv_base = {0, 0};
|
|
|
339 struct timeval tv;
|
|
|
340
|
|
|
341 if (!tv_base.tv_sec)
|
|
|
342 {
|
|
|
343 gettimeofday(&tv_base, NULL);
|
|
|
344 return 0;
|
|
|
345 }
|
|
|
346 gettimeofday(&tv, NULL);
|
|
|
347 return (tv.tv_sec - tv_base.tv_sec) * 1000 +
|
|
|
348 (tv.tv_usec - tv_base.tv_usec) / 1000;
|
|
|
349 }
|
|
|
350
|
|
|
351 /* debugging */
|
|
|
352 int
|
|
|
353 msetime()
|
|
|
354 {
|
|
|
355 struct timeval tv;
|
|
|
356 gettimeofday(&tv, NULL);
|
|
|
357 return (tv.tv_sec - 732737182) * 1000 + tv.tv_usec / 1000;
|
|
|
358 }
|
|
|
359
|
|
|
360 int
|
|
|
361 uchar_diff(x, y)
|
|
|
362 int x, y;
|
|
|
363 {
|
|
|
364 register res;
|
|
|
365
|
|
|
366 res = x - y;
|
|
|
367
|
|
|
368 if (res > 128)
|
|
|
369 return res - 256;
|
|
|
370 else if (res < -128)
|
|
|
371 return res + 256;
|
|
|
372 else
|
|
|
373 return res;
|
|
|
374 }
|
