[Freeciv-Dev] "safe pointers"; was Re: server crash fixes

[David Pfitzner <dwp@xxxxxxxxxxxxxx>]

Jeff Mallatt wrote:

> After percolating up several calls, this could lead to the iterator in
> ai_manage_units() having dangling pointers.  This is similar to the problem
> with disbanding barbarian boats, which was fixed by changing to using
> wipe_unit_safe().  Changing to wipe_unit_safe() in this case, however,
> would be a *BIG* chore.
> 
> So, I settled for re-implementing ai_manage_units() in a way that, I hope,
> will avoid all possible wipe_unit()-caused dangling pointer problems.  This
> is the second patch (safer-ai_manage_units-0.diff).

> Content-Disposition: attachment; filename="boat-lost-segfault-fix-0.diff"

> +         if (!unit_list_find(&pplayer->units, boatid)) return(-1); /* died */

> Content-Disposition: attachment; filename="safer-ai_manage_units-0.diff"
> +      punit = unit_list_find(&pplayer->units, unitids[index]);

For some time I've wanted to generalize the "citycache" in
the server to also include units.  The citycache (not really
a "cache") is a mapping of city id values to city pointers, 
which allows quick lookups based on id values.  Unit ids are 
in the same "space" as city ids, with distinct values, so 
is should be reasonably easy to include unit id mapping too.

Doing so would allow fast lookups on unit id values, which 
would make the above "safe" methods of looking up id values
very fast.  That is, O(1), instead of O(num_player_units).  
In principle you could even change unit lists and iterators 
to use id values instead of pointers (cf unitids[] above), 
thus avoiding all dangling pointer problems for units.  
Ie, in the restricted space of units and cities, id values 
would be like safe pointers (and slower, but not too much).

The main cost of this is the memory for the mapping, though
this is already borne in the server (citycache), and including
units would not be much change.  Since id values are currently
not re-used, there could perhaps be memory savings by using a 
hash instead of an array.  Or you could have a scheme to
re-use id values in a careful way -- ie, delayed reuse
(turn-based?), since otherwise could have trouble with latency, 
with servers and clients using the same id differently.

Its unclear whether the client would benefit noticably from 
the speed advantages of this scheme compared to the current 
slow id->pointer lookups, but if were to use ids in iterators
etc, would probably want to implement in the client too (ie, 
in common), for simplicity.  (Or in principle could have an 
interface which either does the lookups via mapping or via 
slow traversal, like current find_city_by_id(), but I think
not.)

-- David