[crossfire] Proposal: retire MAX_OBJECTS and object allocator

[Mark Wedel]

On 3/9/20 11:24 PM, Kevin Zheng wrote:
> Hi there,
> 
> After experiencing MAX_OBJECTS-related excessive swapping on Invidious
> that allowed Saromok's souped-up goblins to poison and kill my
> character, I've decided to take another look at memory management.
> 
> I may be missing some historical context for why things are the way they
> currently are in Crossfire, so I welcome feedback on what these proposed
> changes might do or not do.

  Crossfire goes way back (30+ years at this point), and the power/abilities of those machines back then were much more limited.  I think back then, the computer I was using had 16 megs of memory.  As such, things like memory consumption was much more a concern, and while memory usage has gone up (more stuff stored in the object, larger maps, etc), it has not gone up at the same pace as computer power has gone up.  So a lot of those old assumptions are no longer true.

> 
> The rationale for each change is included in each patch, but reproduced
> here for convenience:
> 
> 
> Subject: [PATCH 1/2] Retire MAX_OBJECTS
> 
> MAX_OBJECTS has probably outlived its usefulness. It was previously "no
> hard limit," only serving to trigger map swapping immediately after
> loading a map, if the number of used objects exceeded MAX_OBJECTS.
> 
> At worse case, MAX_OBJECTS causes an O(n^2) search and O(n) swaps, where
> n is the number of maps in memory. This happens immediately after
> loading a very large map. The server takes O(n) to search for the map
> with the smallest remaining timeout and swaps it, and does this n times
> or until enough memory is freed. If the other maps are small, this does
> not free much memory and causes the "performance hit" mentioned in the
> comments. This was observed on Invidious, where the server experienced
> delays of up to 700 ms immediately after loading a large map due to
> excessive swapping.
> 
> Removing MAX_OBJECTS does not significantly change the server's
> allocation pattern because the server never frees memory (it maintains
> an internal free list) and because maps are swapped out based on timeout
> at the end of each tick anyway.

  This totally makes sense - as alluded to above, at one time, memory was constrained and one wanted to make sure crossfire did not use so much memory as to cause paging on the system it was running on.  In theory, MAX_OBJECTS would get tuned by each administrator, based on how much memory their server had, but I think that rarely happened.

> 
> 
> Subject: [PATCH 2/2] Retire object allocator
> 
> The object allocator allocates OBJ_EXPAND objects at a time and manages
> its own free list. It is faster at allocating many objects at once, but
> defeats memory debuggers and mitigation techniques. It also does not
> return unused memory to the operating system.

  Not sure if still the case, but at one time, performance of allocating thousands of new objects individually increased lag (when loading new maps).  So doing it in blocks of 500 or whatever was faster.  At one point I had put in option to do individually allocation, simply for the reason above - if using a memory debugger, that block of objects failed to work.

  Minor nit - even free() on a memory object does not return it to the OS - it tells malloc that block of memory is available again, and on a future call, malloc will re-use it, though you can get fragmentation (malloc may decide to use that memory for something smaller than an object).

> 
> Rewrite object_new() to always allocate memory using calloc(). This will
> incur some memory overhead since an object struct does not fit perfectly
> into a nice allocator slab size.

  I suspect additional overhead should be pretty trivial, assuming the allocator is decent (and realistically, not much an issue anyways)

> 
> object_free2() adds freed objects to a free list that is reclaimed at
> the end of each server tick. It cannot immediately free object memory,
> because some callers expect to be able to query it for FLAG_FREED to
> detect object removal.

  querying for flag freed was always a bit buggy (it sort of relies that the given object won't get re-used, which works because the program is singled threaded and these freed objects will be last to be allocated when new objects are needed again).

  Also, as noted above, since memory is not returned to the OS, only the allocator, having crossfire itself keep a freelist makes perfect sense - it is going to need those objects again at some point, and objects are the main use of dynamic memory.   If the program did something like was in one state where it needed a bunch of malloc'd items, and did something with them, no longer needed them, but then needed a large amount of memory for a different object type, freeing them would make sense, because in that second allocation, it could re-use that freed up space.