Mercurial > ~darius > hgwebdir.cgi > paradise_server

comparison src/findslot.c @ 4:aa38447a4b21

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
First entry of Paradise Server 2.9 patch 10 Beta
author darius
date Sat, 06 Dec 1997 04:37:03 +0000
parents
children
comparison
equal deleted inserted replaced
3:cafa94d86546 4:aa38447a4b21
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
20 #include "config.h"
21 #include <stdio.h>
22 #include <sys/types.h>
23 #include <sys/ipc.h>
24 #include <sys/shm.h>
25 #include <errno.h>
26 #include <pwd.h>
27 #include <string.h>
28 #include <ctype.h>
29 #include "defs.h"
30 #include "struct.h"
31 #include "data.h"
32 #include "packets.h"
33 #include "shmem.h"
34
35 int grabslot( /* int */ );
36 void mapWaitCount( /* int */ );
37
38
39 extern int isClientDead();
40 extern unsigned int sleep();
41 extern int sendQueuePacket();
42 extern int flushSockBuf();
43
44 int
45 findslot(overload, homeaway)
46 int overload;
47 enum HomeAway homeaway;
48 {
49 int i;
50
51 i = grabslot(overload, homeaway);
52 players[i].p_pos = -1;
53 memset(&players[i].p_stats, 0, sizeof(struct stats));
54 players[i].p_stats.st_tticks = 1;
55 #if 0
56 for (j = 0; j < 95; j++)
57 {
58 players[i].p_stats.st_keymap[j] = j + 32;
59 }
60 players[i].p_stats.st_keymap[95] = 0;
61 #endif
62 players[i].p_stats.st_flags = ST_INITIAL;
63 return (i);
64 }
65
66 static int
67 allocate_slot(homeaway, overload, allocate)
68 enum HomeAway homeaway;
69 int overload;
70 int allocate;
71 {
72 int i;
73 if (overload)
74 {
75 for (i = MAXPLAYER - 1; i >= 0; i--)
76 {
77 if (players[i].p_status == PFREE)
78 {
79 if (allocate)
80 {
81 players[i].p_status = POUTFIT;
82 players[i].p_team = NOBODY;
83 }
84 return i;
85 }
86 }
87 }
88 else
89 {
90 #ifdef LEAGUE_SUPPORT
91 if (status2->league)
92 {
93 /*
94 * for league play, make sure one team doesn't crowd out the other.
95 */
96 int count = 0;
97 for (i = 0; i < MAXPLAYER; i++)
98 {
99 if (players[i].p_status == PFREE)
100 continue;
101 if (players[i].p_homeaway == homeaway)
102 count++;
103 }
104 if (count * 2 >= MAXPLAYER - configvals->ntesters)
105 return -1; /* our team is full */
106 }
107 #endif
108 for (i = 0; i < MAXPLAYER - configvals->ntesters; i++)
109 {
110 if (players[i].p_status == PFREE)
111 {
112 if (allocate)
113 {
114 players[i].p_status = POUTFIT;
115 players[i].p_team = NOBODY;
116 }
117 return i;
118 }
119 }
120 }
121 return -1;
122 }
123 #if 0
124 static int
125 ImAllowed(slotnum, homeaway)
126 int slotnum;
127 enum HomeAway homeaway;
128 {
129 #ifdef LEAGUE_SUPPORT
130 int half;
131 if (!status2->league)
132 return 1;
133
134 half = (MAXPLAYER - configvals->ntesters) / 2;
135 return (homeaway == AWAY) ? (slotnum < half) :
136 (slotnum >= half);
137 #else
138 return 1;
139 #endif
140 }
141 #endif
142 /*
143 * The following code for grabslot() is really bizarre, and needs an
144 * explaination.
145 *
146 * Basically, the queue works like this: Each process that needs to wait takes
147 * a number, and when that number comes up, the process enters the game.
148 * status->count is the next number to take for a new process, and
149 * status->wait is the current process being served.
150 *
151 * However, this is not enough to determine exactly how many people are waiting,
152 * because people may drop out. So, 3 more variables are added,
153 * status->request posts a request of some sort to all of the other
154 * processes, and status->number is the process posting the request. Also,
155 * status->answer is available for any kind of response needed from the other
156 * processes. (Needless to say, only one process can make a request at any
157 * one time).
158 *
159 * Every process will wait for a second (sleep(1)), and then check the queue
160 * status, do what is appropriate, and repeat.
161 *
162 * Above and beyond this, processes may die, and not report it (for whatever
163 * reason, and every process waiting on the queue watches the behavior of
164 * every other supposed process to make sure it is still alive).
165 *
166 * When a space opens up, and the person who holds the number currently being
167 * served does not respond, then the processes argue over who deserves to get
168 * in next. The first process to decide that no one is going to take the
169 * free slot says that his number is the next on to be served. He waits for
170 * anyone to disagree with him. Any other processes which notice that their
171 * number is lower than the number being served claim that their number is
172 * the next one to be served. They also wait for anyone to disagree with
173 * them. Eventually, everyone is done waiting, and the process with the
174 * lowest count will be served.
175 *
176 * Variables: status->wait: Number being served. status->count: Next
177 * number to take.
178 *
179 * status->request: Process request. (status->number) (status->answer)
180 * REQFREE: No requests pending. REQWHO: How many people are
181 * before me? In this case, every process in from of this process (whose
182 * position is recorded in status->number) increments status->answer.
183 * REQDEAD: I am leaving the queue (Either to quit, or enter game). Any
184 * process whose position is higher than this process will note that they are
185 * closer to the top of the queue.
186 *
187 * (Local) waitWin: The window. qwin: The quit half of waitWin.
188 * countWin: The count half of waitWin. count: My number (Position
189 * in queue). pseudocount: Number of people in front of me (-1 means I don't
190 * know). myRequest: This keeps track of requests I've made. If it is non
191 * zero, then this is the number of times I will leave it there before I get
192 * my answer (if there is one), and reset status->request. idie: This
193 * is set to one if I need to leave the queue. When I get a chance, I will
194 * submit my request, and leave. wearein: This is the slot we grabbed
195 * to enter the game. If it is -1, then we haven't got a slot yet. If we
196 * can grab a slot, then wearein is set to the slot #, and idie is set to 1.
197 *
198 * Because we need to monitor other processes, the following variables also
199 * exist:
200 *
201 * oldcount: The number that was being served last time I looked. waits:
202 * Number of times I've seen oldcount as the number being served. If a
203 * position opens in the game, and no one takes it for a while, we assume
204 * that someone died. lastRequest: The last request I have seen.
205 * lastNumber: The process making this request. reqCount: Number of
206 * times I've seen this request. If I see this request 9 times, I assume it
207 * is obsolete, and I reset it.
208 */
209
210 int
211 grabslot(overload, homeaway)
212 int overload; /* Indicates a request for a tester's slot. */
213 enum HomeAway homeaway;
214 {
215 int count; /* My number */
216 int oldcount; /* Number that was being served last check */
217 int i;
218 int waits; /* # times I have waited for someone else to
219 * act */
220 int oldwait; /* Number being served last check */
221 int pseudocount = -1; /* Count on queue for sake of person waiting */
222 int myRequest = 0; /* To keep track of any request I'm making */
223 int lastRequest = 0; /* Last request I've seen */
224 int lastNumber = 0; /* Last person making request */
225 int reqCount = 0; /* Number of times I've seen this */
226 int idie = 0; /* Do I want to die? */
227 int wearein = -1; /* Slot we got in the game */
228 int rep = 0;
229
230 /* If other players waiting, we get in line behind them */
231 if (!overload && status->wait != status->count)
232 {
233 count = status->count++;
234 }
235 else
236 {
237 /* Get in game if posible */
238 #if 1
239 i = allocate_slot(homeaway, overload, 1);
240 if (i >= 0)
241 return i;
242 #else
243 if (overload)
244 for (i = MAXPLAYER - 1; i >= 0; i--)
245 {
246 if (players[i].p_status == PFREE)
247 { /* We have a free slot */
248 players[i].p_status = POUTFIT; /* possible race code */
249 players[i].p_team = NOBODY;
250 return (i);
251 }
252 }
253 else
254 for (i = 0; i < MAXPLAYER - configvals->ntesters; i++)
255 {
256 if (ImAllowed(i, homeaway)
257 && players[i].p_status == PFREE)
258 { /* We have a free slot */
259 players[i].p_status = POUTFIT; /* possible race code */
260 players[i].p_team = NOBODY;
261 return (i);
262 }
263 }
264 #endif
265 /* Game full. We will wait. */
266 count = status->count++;
267 }
268 waits = 0;
269 oldwait = -1;
270 oldcount = status->wait;
271
272 /* For count = 0,1,2 I know that it is right */
273 if (count - status->wait < 1)
274 {
275 pseudocount = count - status->wait;
276 }
277 for (;;)
278 {
279 /* Send packets occasionally to see if he is accepting... */
280 if (rep++ % 10 == 0)
281 {
282 mapWaitCount(pseudocount);
283 }
284 if (isClientDead())
285 {
286 if (count == status->count - 1)
287 {
288 status->count--;
289 exit(0);
290 }
291 /* If we are at top, decrease it */
292 if (count == status->wait)
293 {
294 status->wait++;
295 }
296 idie = 1;
297 /* break; warning, function has return e and return */
298 exit(0);
299 }
300 if (status->wait != oldcount)
301 {
302 mapWaitCount(pseudocount);
303 oldcount = status->wait;
304 }
305 /* To mimize process overhead and aid synchronization */
306 sleep(1);
307 /* Message from daemon that it died */
308 if (status->count == 0)
309 exit(0);
310 /* I have a completed request? */
311 if (myRequest != 0 && --myRequest == 0)
312 {
313 if (idie && status->request == REQDEAD)
314 {
315 status->request = REQFREE;
316 /* Out of queue, into game */
317 if (wearein != -1)
318 {
319 return (wearein);
320 }
321 exit(0);
322 }
323 pseudocount = status->answer;
324 status->request = REQFREE;
325 if (pseudocount > 18)
326 idie = 1;
327 mapWaitCount(pseudocount);
328 }
329 /* Tell the world I am going bye bye */
330 if (idie && status->request == REQFREE)
331 {
332 status->request = REQDEAD;
333 status->number = count;
334 myRequest = 4;
335 }
336 /* Should I request a count for # of people waiting? */
337 if (pseudocount == -1 && status->request == REQFREE)
338 {
339 status->request = REQWHO;
340 status->number = count;
341 status->answer = 0;
342 myRequest = 4;
343 /* I give people 4 seconds to respond */
344 }
345 /* Is someone else making a request? */
346 if (status->request != REQFREE && myRequest == 0)
347 {
348 if (status->request == lastRequest &&
349 status->number == lastNumber)
350 {
351 reqCount++;
352 /* 9 occurances of the same request implies that the process */
353 /* died. I will reset request. */
354 if (reqCount > 8)
355 {
356 status->request = REQFREE;
357 }
358 }
359 else
360 {
361 lastRequest = status->request;
362 lastNumber = status->number;
363 reqCount = 1;
364 if (lastRequest == REQWHO)
365 {
366 if (count < lastNumber)
367 {
368 status->answer++;
369 }
370 }
371 else if (lastRequest == REQDEAD)
372 {
373 if (count > lastNumber && pseudocount != -1)
374 {
375 pseudocount--;
376 mapWaitCount(pseudocount);
377 }
378 }
379 }
380 }
381 /* If someone raised wait too high, I claim that I * am next in line */
382 if (status->wait > count && !idie)
383 {
384 status->wait = count;
385 /* Give people a chance to correct me */
386 sleep(2);
387 }
388 #if 1
389 if (idie)
390 continue;
391 if (count == status->wait)
392 {
393 i = allocate_slot(homeaway, overload, 1);
394 if (i < 0)
395 continue;
396 status->wait++;
397 wearein = i;
398 idie = 1;
399 }
400 else
401 {
402 i = allocate_slot(homeaway, overload, 0);
403 if (i < 0)
404 continue;
405 if (oldwait == status->wait)
406 {
407 waits++;
408 }
409 else
410 {
411 oldwait = status->wait;
412 waits = 1;
413 }
414 /* If this is our fifth wait (5 sec), then something is */
415 /* wrong. We assume someone died, and fix this problem */
416 if (waits == 5 && !idie)
417 {
418 /* I want to be next in line, so I say so. */
419 status->wait = count;
420 /* And I allow someone to correct me if I'm wrong */
421 sleep(2);
422 waits = 0;
423 }
424
425 }
426 #else
427 for (i = 0; i < MAXPLAYER - configvals->ntesters; i++)
428 {
429 /* If we want to die anyway, we have no right looking for */
430 /* a free slot */
431 if (idie)
432 break;
433 if (ImAllowed(i, homeaway) && players[i].p_status == PFREE)
434 {
435 /* If I am next in line... */
436 if (count == status->wait)
437 {
438 players[i].p_status = POUTFIT;
439 players[i].p_team = NOBODY;
440 /* Increase count for next player */
441 status->wait++;
442 /* I should check idie, but maybe he wants in, eh? */
443 wearein = i;
444 idie = 1;
445 break;
446 }
447 else
448 {
449 if (oldwait == status->wait)
450 {
451 waits++;
452 }
453 else
454 {
455 oldwait = status->wait;
456 waits = 1;
457 }
458 /* If this is our fifth wait (5 sec), then something is */
459 /* wrong. We assume someone died, and fix this problem */
460 if (waits == 5 && !idie)
461 {
462 /* I want to be next in line, so I say so. */
463 status->wait = count;
464 /* And I allow someone to correct me if I'm wrong */
465 sleep(2);
466 waits = 0;
467 }
468 break;
469 }
470 }
471 }
472 #endif
473 /* this location is skipped if we didn't find a slot */
474 }
475 }
476
477 void
478 mapWaitCount(count)
479 unsigned int count;
480 {
481 if (count == -1)
482 return;
483
484 sendQueuePacket((short) count);
485 blk_flag = 1;
486 updateMOTD();
487 blk_flag = 0;
488
489 undeferDeferred(); /* send the MOTD through the TCP buffers */
490 flushSockBuf();
491 }