[crossfire] Proposal: retire MAX_OBJECTS and object allocator

[Kevin Zheng]

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.

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.


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.

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.

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.


These changes were tested locally (mostly by running a character around)
with 1) clang -fsanitize=address, which did not report any errors, and
2) with Jemalloc statistics enabled (see attached, jemalloc.out).

As expected, after the change, the allocator bin seeing the most
activity was 768 bytes (struct object is 656 bytes on x86-64).

-- 
Kevin Zheng
kevinz5000 at gmail.com | kevinz at berkeley.edu
XMPP: kevinz at eecs.berkeley.edu
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-Retire-MAX_OBJECTS.patch
Type: text/x-patch
Size: 8575 bytes
Desc: not available
URL: <http://mailman.metalforge.org/pipermail/crossfire/attachments/20200309/93de7f08/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0002-Retire-object-allocator.patch
Type: text/x-patch
Size: 11623 bytes
Desc: not available
URL: <http://mailman.metalforge.org/pipermail/crossfire/attachments/20200309/93de7f08/attachment-0001.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: jemalloc.out
Type: text/x-maxima-out
Size: 16044 bytes
Desc: not available
URL: <http://mailman.metalforge.org/pipermail/crossfire/attachments/20200309/93de7f08/attachment-0002.bin>