Entity List Management in Q2 Mods

[QwazyWabbit]

Several extensive attempts were made to crash the Loxophilia server via the entity list crash pathway. These attempts did not succeed. The crash is produced when the active entity list is filled and a subseqent call to G_Spawn in the game mod can't find space in the entity list to instantiate a new entity. The function fails with a call to gi.error ("ED_Alloc: no free edicts"); which halts the game server resulting in a temporary denial of service.

There are two factors influencing this relative immunity to DoS.

1. Entity list size: old game default is 1024 entities. Loxo uses 2048 by default.
2. List management code in LOX was modified long ago and is now an historic artifact in LOX.

Three functions were modified in g_utils.c to speed up entity initialization and freeing.
The functions are listed below. These functions are common to all Quake2 mods.
NOTE: The entity member "classnum" is used in LOX to speed up class comparisons instead of using string matching based on "classname". The CN_* values are simply #defines or enumated constants for all entity classes in the relevant mod. You may freely discard the code dealing with this data member.

Code: [Select]

void G_InitEdict (edict_t *e)
{
e->inuse = QTRUE;
e->classname = "noclass";
e->classnum = CN_NOCLASS;
e->gravity = 1.0;
e->s.number = e - g_edicts;

// Clear what the free-edict list may have set.
e->chain = NULL;

// This is another headache.
e->think = NULL;
e->nextthink = 0;
}

// The free-edict list.  Meant to vastly speed up G_Spawn().
edict_t *g_freeEdictsH = NULL;
edict_t *g_freeEdictsT = NULL;

/*
=================
G_Spawn

Either finds a free edict, or allocates a new one.
Try to avoid reusing an entity that was recently freed, because it
can cause the client to think the entity morphed into something else
instead of being removed and recreated, which can cause interpolated
angles and bad trails.
=================
*/

edict_t *G_Spawn (void)
{
int i;
edict_t *e;
// char string[64];

// If the free-edict queue can help, let it.
while (g_freeEdictsH != NULL)
{
// Remove the first item.
e = g_freeEdictsH;
g_freeEdictsH = g_freeEdictsH->chain;
if (g_freeEdictsH == NULL)
g_freeEdictsT = NULL;

// If it's in use, get another one.
if (e->inuse)
continue;

// If it's safe to use it, do so.
if (e->freetime < 2 || level.time - e->freetime > 0.5)
{
G_InitEdict (e);
return e;
}

// If we can't use it, we won't be able to use any of these -- anything
// after it in the queue was freed even later.
else
break;
}

// The old way to find a free edict.
e = &g_edicts[(int)maxclients->value+1];
for ( i = (int) maxclients->value + 1 ; i < globals.num_edicts ; i++, e++)
{
// the first couple seconds of server time can involve a lot of
// freeing and allocating, so relax the replacement policy
if (!e->inuse && ( e->freetime < 2 || level.time - e->freetime > 0.5 ) )
{
G_InitEdict (e);
return e;
}
}

if (i == game.maxentities)
gi.error ("ED_Alloc: no free edicts");

globals.num_edicts++;
G_InitEdict (e);
// sprintf(string, "num_edicts is %i\n", globals.num_edicts);
// OutputDebugString(string);
return e;
}

/*
=================
G_FreeEdict

Marks the edict as free
=================
*/
void G_FreeEdict (edict_t *ed)
{
gi.unlinkentity (ed); // unlink from world

if ((ed - g_edicts) <= (maxclients->value + BODY_QUEUE_SIZE))
{
// gi.dprintf("tried to free special edict\n");
return;
}

memset (ed, 0, sizeof(*ed));
ed->classname = "freed";
ed->classnum = CN_NOCLASS;
ed->freetime = level.time;
ed->inuse = QFALSE;

// Put this edict into the free-edict queue.
if (g_freeEdictsH == NULL)
g_freeEdictsH = ed;
else
g_freeEdictsT->chain = ed;
g_freeEdictsT = ed;
ed->chain = NULL;
}

In server configuration files you can set maxentities 2048 or you can modify g_save.c in the game source:

Code: [Select]

maxentities = gi.cvar ("maxentities", "2048", CVAR_LATCH);


[kren.Z]

Syntax Highlighting - http://pastie.org/3639603


Good stuff Qwazzy. I was able to reach the maximum entity limit with a single client. I'm currently writing a python script to enumerate max clients and believe it's possible to create a scenario in which most of the gameplay remains unrendered and thus invisible, leaving only the re-allocation of the 2048 entities visible. (hhm...  A CLUSTER GRENADE OUT OF NOWHERE!?!? hehe). This is due to a flaw in which the mod increments ammo pickup.





Cool mod btw

[skuller]

You can't have more than 1024 entities in Q2 without bumping MAX_EDICTS constant and thus changing the network protocol. Setting ‘maxentities’ cvar alone to 2048 won't help (once 1025'th entity is allocated server will crash anyway).

[QwazyWabbit]

Interesting point. But then why does the cvar maxentities exist and why is globals.max_edicts set to game.maxentities in g_save.c in the historical game mod?
And why does this line exist in the same code"

Code: [Select]

g_edicts =  gi.TagMalloc (game.maxentities * sizeof(g_edicts[0]), TAG_GAME);


[skuller]

Perhaps there was intent to make maxentities completely configurable, but that never got implemented in server and client. As a result, game allocates memory for entity array dynamically, while client and server use fixed arrays. Actually, ge->max_edicts field is never referenced by 3.20 server code, but in many places server implicitly assumes ge->num_edicts to be less than MAX_EDICTS. If server encounters an active entity beyond MAX_EDICTS, bad things will happen (server may silently overwrite memory).

So it is a good idea for a mod author to verify that maxclients < maxentities <= MAX_EDICTS at server startup.

[QwazyWabbit]

No, there is a difference between game entities, server entities and client entities. The MAX_EDICTS limit is only for those entities that must be passed from server to client. It's perfectly acceptable to have more entities in the game than are passed to the client.

[skuller]

You seem to be mixing up MAX_PACKET_ENTITIES (maximum number of entities in client frame, which is 128) and MAX_EDICTS (maximum number of entities in game from server and client points of view).

[QwazyWabbit]

I don't think so but I'd like to read your thoughts on why the Loxo server has not crashed with ED_Alloc: no free edicts nor has it crashed with SEG-FAULT or bad data overwrites. Typical LOX num_edicts runs in the 500 to 700 range on 12 players and custom maps. It's been a long time since the server had a heavy load.

I'll bring maxentities down to 1024 for a while and see what happens when krenZ has his way with it again. It's quite possible the faster spawn search is responsible and not the size of the entity array.

But why does it say this in the original game.h?

Code: [Select]

//
// global variables shared between game and server
//

// The edict array is allocated in the game dll so it
// can vary in size from one game to another.
//
// The size will be fixed when ge->Init() is called
struct edict_s *edicts;
int edict_size;
int num_edicts; // current number, <= max_edicts
int max_edicts;


[skuller]

I don't think so but I'd like to read your thoughts on why the Loxo server has not crashed with ED_Alloc: no free edicts nor has it crashed with SEG-FAULT or bad data overwrites. Typical LOX num_edicts runs in the 500 to 700 range on 12 players and custom maps. It's been a long time since the server had a heavy load.

Most likely it has never hit the 1024 entities limit. R1Q2 server will almost definitely crash once an attempt to link an entity beyond MAX_EDICTS is done.

But why does it say this in the original game.h?

Well that comment is generally true. It just needs to mention that server can handle not more than 1024 entities.

[quadz]

Over the weekend I tinkered with the souce code of an old server-side bot, called "3rd Zigock II" (v097). It had routes for the *64 maps, and being curious what the *64 maps would look like with 128 clients I increased its MAX_BOTS hard limit from 64 to 128, and tried it out.

Unfortunately it hit the familiar "ED_Alloc: no free edicts" error within a few seconds.

Turns out it's mostly gibs that were taking up slots.

What I ended up doing was adding a mechanism called by G_RunFrame that attempts to maintain a free pool of edicts, by purging nonessential entities (like gibs) if space starts getting low.

Was then able to run 128 bots on the *64 maps with no problem.

Code: [Select]


diff --git a/src/g_local.h b/src/g_local.h
index a62d518..821a0b3 100644
--- a/src/g_local.h
+++ b/src/g_local.h
@@ -652,6 +652,11 @@ void Touch_Item(edict_t *ent, edict_t *other, cplane_t *plane, csurface_t *surf)
 //
 // g_utils.c
 //
+
+// tsmod: somewhat arbitrary, but pool should be more than would
+// be created in a single frame (aiming for supporting maxclients=128)
+#define EMERGENCY_ENTITY_FREE_POOL_SIZE                (128+32)
+
 qboolean    KillBox(edict_t *ent);
 void    G_ProjectSource(vec3_t point, vec3_t distance, vec3_t forward, vec3_t right, vec3_t result);
 edict_t *G_Find(edict_t *from, int fieldofs, char *match);
@@ -663,6 +668,8 @@ void    G_SetMovedir(vec3_t angles, vec3_t movedir);
 void    G_InitEdict(edict_t *e);
 edict_t *G_Spawn(void);
 void    G_FreeEdict(edict_t *e);
+void   G_EmergencyMaintainMinimumFreeEntityPool(int pool_size);
+qboolean G_EntityUseNearEmergencyThreshold(void);

 void    G_TouchTriggers(edict_t *ent);
 void    G_TouchSolids(edict_t *ent);


diff --git a/src/g_main.c b/src/g_main.c
index d318d4c..b7a7d20 100644
--- a/src/g_main.c
+++ b/src/g_main.c
@@ -510,6 +510,8 @@ void G_RunFrame(void)
         return;
     }

+       G_EmergencyMaintainMinimumFreeEntityPool(EMERGENCY_ENTITY_FREE_POOL_SIZE);  // tsmod
+
 //
 // Bot Spawning
 //
 
 
diff --git a/src/g_misc.c b/src/g_misc.c
index 8147277..57334b5 100644
--- a/src/g_misc.c
+++ b/src/g_misc.c
@@ -127,6 +127,9 @@ void ThrowGib(edict_t *self, char *gibname, int damage, int type)
     vec3_t  size;
     float   vscale;

+       if (G_EntityUseNearEmergencyThreshold())  // tsmod
+               return;
+
     gib = G_Spawn();

     VectorScale(self->size, 0.5, size);
@@ -170,6 +173,9 @@ void ThrowHead(edict_t *self, char *gibname, int damage, int type)
     vec3_t  vd;
     float   vscale;

+       if (G_EntityUseNearEmergencyThreshold())  // tsmod
+               return;
+
     self->s.skinnum = 0;
     self->s.frame = 0;
     VectorClear(self->mins);
@@ -215,6 +221,9 @@ void ThrowHead2(edict_t *self, char *gibname, int damage, int type)
     vec3_t  vd;
     float   vscale;

+       if (G_EntityUseNearEmergencyThreshold())  // tsmod
+               return;
+
     self->s.skinnum = 0;
     self->s.frame = 0;
     VectorClear(self->mins);
@@ -258,6 +267,9 @@ void ThrowClientHead(edict_t *self, int damage)
     vec3_t  vd;
     char    *gibname;

+       if (G_EntityUseNearEmergencyThreshold())  // tsmod
+               return;
+
     if (rand() & 1) {
         gibname = "models/objects/gibs/head2/tris.md2";
         self->s.skinnum = 1;        // second skin is player
         

diff --git a/src/g_save.c b/src/g_save.c
index d6a9b32..24358e1 100644
--- a/src/g_save.c
+++ b/src/g_save.c
@@ -210,6 +210,8 @@ void InitGame(void)

     // initialize all entities for this game
     game.maxentities = maxentities->value;
+       if (game.maxentities > MAX_EDICTS)  // tsmod: enforce hard protocol limit
+               game.maxentities = MAX_EDICTS;
     g_edicts =  gi.TagMalloc(game.maxentities * sizeof(g_edicts[0]), TAG_GAME);
     globals.edicts = g_edicts;
     globals.max_edicts = game.maxentities;
     
diff --git a/src/g_utils.c b/src/g_utils.c
index 72cd481..3543dac 100644
--- a/src/g_utils.c
+++ b/src/g_utils.c
@@ -375,6 +375,7 @@ void G_InitEdict(edict_t *e)
     e->classname = "noclass";
     e->gravity = 1.0;
     e->s.number = e - g_edicts;
+       e->freetime = level.time;  // tsmod: time now also marked at init, for emergency reclaim logic
 }

 /*
@@ -392,20 +393,28 @@ edict_t *G_Spawn(void)
 {
     int         i;
     edict_t     *e;
-
-    e = &g_edicts[(int)maxclients->value + 1];
-    for (i = maxclients->value + 1 ; i < globals.num_edicts ; i++, e++) {
-        // the first couple seconds of server time can involve a lot of
-        // freeing and allocating, so relax the replacement policy
-        if (!e->inuse && (e->freetime < 2 || level.time - e->freetime > 0.5)) {
-            G_InitEdict(e);
-            return e;
-        }
-    }
-
-    if (i == game.maxentities) {
-        gi.error("ED_Alloc: no free edicts");
-    }
+       int                     attempt;
+       const int       MAX_ATTEMPTS = 2;
+
+       for (attempt = 1; attempt <= MAX_ATTEMPTS; ++attempt) {
+               qboolean permit_recently_freed = (attempt > 1);
+
+               i = (int)maxclients->value + 1;
+               e = &g_edicts[i];
+               for ( ; i < globals.num_edicts ; i++, e++) {
+                       // the first couple seconds of server time can involve a lot of
+                       // freeing and allocating, so relax the replacement policy
+                       // tsmod: emergency allow reclaiming any free entity on second pass
+                       if (!e->inuse && (permit_recently_freed || (e->freetime < 2 || level.time - e->freetime > 0.5))) {
+                               G_InitEdict(e);
+                               return e;
+                       }
+               }
+       }
+
+       if (i >= game.maxentities) {
+               gi.error("ED_Alloc: no free edicts");
+       }

     globals.num_edicts++;
     G_InitEdict(e);
@@ -434,6 +443,97 @@ void G_FreeEdict(edict_t *ed)
     ed->inuse = false;
 }
 
+/* (tsmod)
+=================
+emergencyReclaimNonessentialEntity
+
+Free oldest inUse entity considered nonessential.
+=================
+*/
+#define MAX_RECLAIM_SEVERITY 2
+
+static qboolean entityIsNonessential(const edict_t *e, int severity)
+{
+       qboolean is_gib = ((e->s.effects & EF_GIB) && e->think == G_FreeEdict);
+       qboolean is_dropped_item = (e->spawnflags & DROPPED_ITEM) && !(e->spawnflags & DROPPED_PLAYER_ITEM);
+       qboolean is_missile = (e->movetype == MOVETYPE_FLYMISSILE && e->think == G_FreeEdict);
+       return is_gib || ((severity > 0) && is_dropped_item) || ((severity > 1) && is_missile);
+}
+
+static edict_t *emergencyReclaimNonessentialEntity(int severity)
+{
+    int         i;
+    edict_t     *e;
+       edict_t         *nonessential = NULL;
+
+       i = (int)maxclients->value + BODY_QUEUE_SIZE + 1;
+       e = &g_edicts[i];
+       for ( ; i < globals.num_edicts ; i++, e++) {
+               if (! e->inuse)
+                       continue;
+
+               if (entityIsNonessential(e, severity)) {
+                       if (nonessential == NULL  ||  (e->freetime < nonessential->freetime)) {
+                               nonessential = e;
+                       }
+               }
+       }
+
+       if (nonessential != NULL) {
+               gi.dprintf("reclaiming nonessential entity %d severity %d age %f\n", (int)(nonessential - g_edicts), severity, (float)(level.time - nonessential->freetime));
+
+               G_FreeEdict(nonessential);
+       }
+
+       return nonessential;
+}
+/* (tsmod)
+=================
+G_EmergencyMaintainMinimumFreeEntityPool
+
+Intended to be called by G_RunFrame, maintains <pool_size> free edicts
+by freeing what are considered to be nonessential entities, as necessary.
+The idea is to maintain sufficient free edicts per frame that G_Spawn
+never hits the fatal ED_Alloc error.
+
+The reason we don't call EmergencyReclaimNonessentialEntity on-demand
+from within G_Spawn is that we don't know what entity pointers might be
+referenced on the caller's stack, and we don't want to free something
+that might be being manipulated. Instead, the assumption is that doing
+the work from G_RunFrame is safer, since we can guarantee that at least
+no entity pointers are being manipulated by any caller.
+=================
+*/
+void G_EmergencyMaintainMinimumFreeEntityPool(int pool_size)
+{
+       int severity;
+
+       for (severity = 0; severity <= MAX_RECLAIM_SEVERITY; ++severity) {
+               for (;;) {
+                       edict_t *freed;
+
+                       int num_free = (game.maxentities - globals.num_edicts);
+                       if (num_free >= pool_size) {
+                               return;
+                       }
+
+                       freed = emergencyReclaimNonessentialEntity(severity);
+                       if (freed == NULL) {
+                               gi.dprintf("Warning: insufficient nonessential for emergency edict pool @ severity %d (have %d want %d)\n", severity, num_free, pool_size);
+                               break;
+                       }
+               }
+       }
+}
+
+qboolean G_EntityUseNearEmergencyThreshold(void)
+{
+       const int pool_proximity_threshold = 32;  // arbitrary
+       int num_free = (game.maxentities - globals.num_edicts);
+       return num_free < (EMERGENCY_ENTITY_FREE_POOL_SIZE + pool_proximity_threshold);
+}
+

 /*
 ============