< Summary

Class:Itinero.Data.GlobalNetworkManager
Assembly:Itinero
File(s):/home/runner/work/routing2/routing2/src/Itinero/Data/GlobalNetworkManager.cs
Covered lines:92
Uncovered lines:38
Coverable lines:130
Total lines:388
Line coverage:70.7% (92 of 130)
Covered branches:36
Total branches:48
Branch coverage:75% (36 of 48)
Tag:284_38118444584

Metrics

MethodBranch coverage Cyclomatic complexity Line coverage
.ctor()100%1100%
get_VertexIdSet()100%10%
get_EdgeIdSet()100%1100%
TryClaimBoundaryCrossing(...)100%4100%
get_PendingBoundaryCrossingCount()100%1100%
AddPendingRestriction(...)100%1100%
get_ParkWaits()0%20%
RecordWaitNoLock(...)100%6100%
ParkNoLock(...)100%8100%
RetryPendingRestrictionsFor(...)90%2083.72%
RetryPendingRestrictions(...)0%80%
get_PendingRestrictionCount()100%1100%

File(s)

/home/runner/work/routing2/routing2/src/Itinero/Data/GlobalNetworkManager.cs

#LineLine coverage
 1using System;
 2using System.Collections.Concurrent;
 3using System.Collections.Generic;
 4using System.Threading;
 5using Itinero.Network;
 6using Itinero.Network.Tiles.Standalone.Global;
 7
 8namespace Itinero.Data;
 9
 10/// <summary>
 11/// A manager to manage mapping or vertex and edge ids and turn restrictions.
 12/// </summary>
 13/// <remarks>
 14/// Safe for concurrent tile insertion. Every structure here is bookkeeping that spans tiles —
 15/// the tile data itself lives in the tiles — so this is what several inserts running at once
 16/// contend on, and each piece needs a different guarantee:
 17///
 18/// <list type="bullet">
 19/// <item>the id sets only ever gain independent entries, so a concurrent dictionary is enough;</item>
 20/// <item>a boundary crossing has to be claimed <b>atomically</b> — two tiles must not both
 21/// believe they matched the same crossing and each create the edge;</item>
 22/// <item>pending restrictions are scanned and removed as a batch, which a concurrent collection
 23/// cannot express, so they keep a lock and it is held inside this class rather than left to
 24/// callers to remember.</item>
 25/// </list>
 26/// </remarks>
 27public class GlobalNetworkManager
 28{
 29    /// <summary>
 30    /// Creates a new global network manager.
 31    /// </summary>
 12632    public GlobalNetworkManager()
 12633    {
 12634        this.VertexIdSet = new GlobalVertexIdSet();
 12635        this.EdgeIdSet = new GlobalEdgeIdSet();
 12636    }
 37
 38    /// <summary>
 39    /// The global vertex id set.
 40    /// </summary>
 041    public GlobalVertexIdSet VertexIdSet { get; }
 42
 43    /// <summary>
 44    /// The global edge id set.
 45    /// </summary>
 1787046    public GlobalEdgeIdSet EdgeIdSet { get; }
 47
 48    /// <summary>
 49    /// Pending boundary crossings keyed by GlobalEdgeId.
 50    /// When a crossing's matching tile isn't loaded yet, store the local vertex and metadata here.
 51    /// When the other tile loads and has a crossing with the same GlobalEdgeId, it creates the edge.
 52    /// </summary>
 12653    private readonly ConcurrentDictionary<GlobalEdgeId, (VertexId vertex,
 12654        IEnumerable<(string key, string value)> attributes, uint edgeTypeId, bool isIncoming)>
 12655        _pendingBoundaryCrossings = new();
 56
 57    /// <summary>
 58    /// Claims the pending half of a boundary crossing, or records this half and waits for the other.
 59    /// </summary>
 60    /// <param name="globalEdgeId">The crossing's global edge id.</param>
 61    /// <param name="half">This tile's half of the crossing.</param>
 62    /// <param name="other">The other half, when this call claimed it.</param>
 63    /// <returns>True when the pair is complete and the caller should create the edge.</returns>
 64    /// <remarks>
 65    /// The claim is what makes this safe: exactly one of the two tiles gets <c>true</c>, because
 66    /// <c>TryRemove</c> hands the stored half to a single caller. A read-then-remove would let
 67    /// both tiles see the other's half and both create the edge — which is the kind of race that
 68    /// produces a duplicated boundary edge rather than an exception.
 69    ///
 70    /// A failed <c>TryAdd</c> must retry the claim rather than give up, and that is not a
 71    /// refinement — it is the difference between working and silently losing edges. Both halves
 72    /// can arrive at once: each finds nothing to claim, then one wins the add and the other's
 73    /// <c>TryAdd</c> fails. Returning false there drops the losing half entirely and leaves the
 74    /// winner's half waiting for a partner that has already been and gone, so the boundary edge
 75    /// is never created. Looping turns that lost race into a claim, because the other half is
 76    /// necessarily present the moment the add fails.
 77    ///
 78    /// The loop terminates: a crossing has exactly two halves, so at most one add can be lost.
 79    /// </remarks>
 80    public bool TryClaimBoundaryCrossing(GlobalEdgeId globalEdgeId,
 81        (VertexId vertex, IEnumerable<(string key, string value)> attributes, uint edgeTypeId,
 82            bool isIncoming) half,
 83        out (VertexId vertex, IEnumerable<(string key, string value)> attributes, uint edgeTypeId,
 84            bool isIncoming) other)
 366485    {
 368086        while (true)
 368087        {
 548288            if (_pendingBoundaryCrossings.TryRemove(globalEdgeId, out other)) return true;
 374089            if (_pendingBoundaryCrossings.TryAdd(globalEdgeId, half)) return false;
 1690        }
 366491    }
 92
 93    /// <summary>
 94    /// How many boundary crossings are still waiting for their other half.
 95    /// </summary>
 5596    public int PendingBoundaryCrossingCount => _pendingBoundaryCrossings.Count;
 97
 98    /// <summary>
 99    /// Restrictions that couldn't be resolved yet because not all edges are available.
 100    /// </summary>
 126101    private readonly List<GlobalRestriction> _pendingRestrictions = new();
 102
 126103    private readonly object _pendingRestrictionsLock = new();
 104
 105    /// <summary>
 106    /// <see cref="_pendingRestrictions"/>.Count, readable without the lock.
 107    /// </summary>
 108    /// <remarks>
 109    /// Only ever read to answer "is there anything at all to do", and a stale zero is harmless:
 110    /// whoever adds a restriction publishes the new count after adding it, and the retry that
 111    /// misses it runs on the next insert instead. Restrictions are resolved eventually, not
 112    /// immediately, which is already how the deferred queue works.
 113    /// </remarks>
 114    private int _pendingRestrictionCount;
 115
 116    /// <summary>
 117    /// Pending restrictions indexed by the ways they name.
 118    /// </summary>
 119    /// <remarks>
 120    /// Without this, every insert retried every pending restriction. Measured over one cold block:
 121    /// 7,157 retry passes examined 535,147 restrictions and resolved 2,335 — a 0.44% hit rate, with
 122    /// ~75 permanently unresolvable restrictions re-walked by every later insert. Cost quadratic in
 123    /// tiles, and it made restriction resolution ~39% of tile insertion.
 124    ///
 125    /// Keyed on the <b>way</b> (<see cref="GlobalEdgeId.EdgeId"/>), not the full edge id, because
 126    /// the resolver does not require the exact id a restriction names: it falls back to
 127    /// <c>WalkFromAnchor</c>, which tries every sub-span <c>(EdgeId, anchor, other)</c> of the same
 128    /// way. So the id that arrives is usually a *piece* of the way the restriction asked for, and
 129    /// indexing by exact id parks restrictions under keys that never arrive. Two turn-restriction
 130    /// tests caught exactly that. Inversion needs no special handling here — it swaps tail and head
 131    /// and leaves the way alone.
 132    ///
 133    /// Every way a restriction names is indexed, not just one, so it is retried whenever any of
 134    /// them gains an edge. A resolved restriction leaves its other entries behind; they are
 135    /// filtered by <see cref="_pending"/> on the way out and cleared by the next full sweep.
 136    /// </remarks>
 126137    private readonly Dictionary<long, List<GlobalRestriction>> _pendingByWay = new();
 138
 139    /// <summary>
 140    /// Which restrictions are still pending, so a stale index entry can be recognised.
 141    /// </summary>
 126142    private readonly HashSet<GlobalRestriction> _pending = new();
 143
 144    /// <summary>
 145    /// Records a restriction whose edges are not all loaded yet.
 146    /// </summary>
 147    public void AddPendingRestriction(GlobalRestriction restriction)
 576148    {
 576149        lock (_pendingRestrictionsLock)
 576150        {
 576151            _pendingRestrictions.Add(restriction);
 576152            this.ParkNoLock(restriction);
 576153            Volatile.Write(ref _pendingRestrictionCount, _pendingRestrictions.Count);
 576154        }
 576155    }
 156
 157    /// <summary>
 158    /// How long a parked restriction waits, measured in inserts.
 159    /// </summary>
 160    /// <remarks>
 161    /// The question this answers: is parking a property of the data, or an artifact of the order
 162    /// tiles happen to be inserted in? A restriction at a tile boundary can only resolve once the
 163    /// boundary edge exists, and that edge is created by whichever of the two tiles is inserted
 164    /// second — so the restriction in the first one parks even though its partner arrives
 165    /// milliseconds later in the same batch of nine.
 166    ///
 167    /// If the waits cluster under ~9 inserts, parking is intra-batch ordering and the fix is to
 168    /// resolve after the batch rather than per tile. If they are long, the edges genuinely live
 169    /// outside the batch and the retry has to stay.
 170    /// </remarks>
 126171    private readonly Dictionary<GlobalRestriction, int> _parkedAt = new();
 172
 173    private int _insertSeq;
 174
 175    private long _waitSum;
 176
 177    private int _waitCount;
 178
 179    private int _waitMax;
 180
 181    private int _waitWithinBatch;
 182
 183    /// Parked-restriction waits: how many inserts passed before each resolved.
 184    public (int count, double meanInserts, int maxInserts, int withinBatch) ParkWaits
 185    {
 186        get
 0187        {
 0188            lock (_pendingRestrictionsLock)
 0189            {
 0190                return (_waitCount, _waitCount == 0 ? 0 : _waitSum / (double)_waitCount,
 0191                    _waitMax, _waitWithinBatch);
 192            }
 0193        }
 194    }
 195
 196    /// Records how long a restriction waited. Caller holds the lock.
 197    private void RecordWaitNoLock(GlobalRestriction restriction)
 576198    {
 576199        if (!_parkedAt.Remove(restriction, out var parkedAt)) return;
 200
 576201        var waited = _insertSeq - parkedAt;
 576202        _waitSum += waited;
 576203        _waitCount++;
 674204        if (waited > _waitMax) _waitMax = waited;
 205
 206        // Nine is the batch: VertexTouched loads a tile plus its eight neighbours together.
 1139207        if (waited <= 9) _waitWithinBatch++;
 576208    }
 209
 210    /// Indexes a restriction under every way it names. Caller holds the lock.
 211    private void ParkNoLock(GlobalRestriction restriction)
 576212    {
 576213        _pending.Add(restriction);
 1152214        if (!_parkedAt.ContainsKey(restriction)) _parkedAt[restriction] = _insertSeq;
 4032215        foreach (var edge in restriction)
 1152216        {
 1152217            if (!_pendingByWay.TryGetValue(edge.EdgeId, out var waiting))
 263218            {
 263219                waiting = new List<GlobalRestriction>(1);
 263220                _pendingByWay[edge.EdgeId] = waiting;
 263221            }
 222
 223            // A restriction naming the same way twice (a U-turn) would otherwise be retried
 224            // twice for one arrival.
 1732225            if (!waiting.Contains(restriction)) waiting.Add(restriction);
 1152226        }
 576227    }
 228
 229    /// <summary>
 230    /// Inserts between full sweeps of the pending list.
 231    /// </summary>
 232    /// <remarks>
 233    /// The index above is the mechanism; this is the safety net for the one case it cannot see — a
 234    /// restriction parked under an edge that is already present, so no arrival will ever probe its
 235    /// key. Rare (it needs the race in <see cref="FirstMissingEdge"/>), but a restriction stuck
 236    /// forever is a missing turn restriction, which is a correctness bug, not a slow one.
 237    ///
 238    /// It is also what bounds how much later a restriction can resolve than it used to. Measured
 239    /// at 512, one cold block resolved 2,271 pending restrictions against 2,335 before — 64 were
 240    /// still waiting when the block ended. A server keeps inserting and would resolve them; a
 241    /// finite run does not, and a turn restriction that is briefly absent lets a route take a
 242    /// forbidden turn. At 64 the residue window is 8x smaller and the sweep still costs ~1/64 of
 243    /// the unconditional pass.
 244    /// </remarks>
 245    private const int SweepInterval = 64;
 246
 247    private int _insertsSinceSweep;
 248
 249    /// <summary>
 250    /// Retries the restrictions waiting for any of the edges that just became available.
 251    /// </summary>
 252    /// <param name="arrived">Global edge ids registered by the insert that just ran.</param>
 253    /// <param name="tryResolve">Attempts one restriction; true when it resolved.</param>
 254    public void RetryPendingRestrictionsFor(IReadOnlyList<GlobalEdgeId> arrived,
 255        Func<GlobalRestriction, bool> tryResolve)
 1928256    {
 257        // Same lock-free fast path as the full sweep: nothing pending, nothing to do, and this
 258        // runs on every insert.
 1928259        if (Volatile.Read(ref _pendingRestrictionCount) == 0)
 1138260        {
 261            // Still count the insert, so a sweep is not skipped forever by empty fast paths and so
 262            // the wait measurement is against a clock that keeps moving.
 1138263            Interlocked.Increment(ref _insertsSinceSweep);
 1138264            Interlocked.Increment(ref _insertSeq);
 1138265            return;
 266        }
 267
 790268        Interlocked.Increment(ref _insertSeq);
 790269        var sweep = Interlocked.Increment(ref _insertsSinceSweep) >= SweepInterval;
 790270        if (sweep)
 0271        {
 0272            Volatile.Write(ref _insertsSinceSweep, 0);
 0273            this.RetryPendingRestrictions(tryResolve);
 0274            return;
 275        }
 276
 790277        var examined = 0;
 790278        var resolved = 0;
 790279        lock (_pendingRestrictionsLock)
 790280        {
 845281            if (_pendingByWay.Count == 0) return;
 282
 283            // Distinct ways only: a tile contributes hundreds of edges but they belong to far
 284            // fewer ways, and one lookup per way is the point of the index.
 735285            var ways = new HashSet<long>();
 8577286            foreach (var edge in arrived) ways.Add(edge.EdgeId);
 287
 3677288            foreach (var way in ways)
 736289            {
 737290                if (!_pendingByWay.TryGetValue(way, out var waiting)) continue;
 291
 292                // Snapshot: tryResolve can re-park a restriction, which appends to this list.
 4430293                for (var i = waiting.Count - 1; i >= 0; i--)
 1480294                {
 1480295                    var restriction = waiting[i];
 296
 297                    // Resolved through one of its other ways already.
 1480298                    if (!_pending.Contains(restriction))
 0299                    {
 0300                        waiting.RemoveAt(i);
 0301                        continue;
 302                    }
 303
 1480304                    examined++;
 2384305                    if (!tryResolve(restriction)) continue;
 306
 576307                    resolved++;
 576308                    this.RecordWaitNoLock(restriction);
 576309                    _pending.Remove(restriction);
 576310                    _pendingRestrictions.Remove(restriction);
 576311                    waiting.RemoveAt(i);
 576312                }
 313
 996314                if (waiting.Count == 0) _pendingByWay.Remove(way);
 735315            }
 316
 735317            Volatile.Write(ref _pendingRestrictionCount, _pendingRestrictions.Count);
 735318        }
 319
 1928320    }
 321
 322    /// <summary>
 323    /// Retries every pending restriction, dropping the ones that now resolve.
 324    /// </summary>
 325    /// <param name="tryResolve">Attempts one restriction; true when it resolved.</param>
 326    /// <remarks>
 327    /// The lock spans the whole pass because the operation is a scan-and-remove over the list,
 328    /// which no concurrent collection expresses: an index-based removal is only meaningful while
 329    /// the list cannot shift underneath it.
 330    ///
 331    /// Note what this means for the caller — <paramref name="tryResolve"/> runs while the lock is
 332    /// held, and it writes turn costs to arbitrary tiles. So restriction resolution serialises
 333    /// against itself across all concurrent inserts. That is deliberate: restrictions name edges
 334    /// in tiles that cannot be predicted from the tile being inserted, so they cannot be
 335    /// partitioned by tile the way edges can. They are also rare compared to edges.
 336    /// </remarks>
 337    public void RetryPendingRestrictions(Func<GlobalRestriction, bool> tryResolve)
 0338    {
 339        // Lock-free when there is nothing to retry, which is the overwhelming majority of
 340        // inserts. This pass runs on EVERY tile insert, so taking the lock unconditionally made
 341        // it a global serialisation point for all concurrent inserts — measured at 29.6% of all
 342        // blocked time in cold, plus another 8.7% on the add side, for a list that is almost
 343        // always empty.
 0344        if (Volatile.Read(ref _pendingRestrictionCount) == 0) return;
 345
 0346        lock (_pendingRestrictionsLock)
 0347        {
 0348            var examined = _pendingRestrictions.Count;
 0349            var resolved = 0;
 0350            for (var i = _pendingRestrictions.Count - 1; i >= 0; i--)
 0351            {
 0352                if (tryResolve(_pendingRestrictions[i]))
 0353                {
 0354                    this.RecordWaitNoLock(_pendingRestrictions[i]);
 0355                    _pendingRestrictions.RemoveAt(i);
 0356                    resolved++;
 0357                }
 0358            }
 359
 360            // Rebuild the index from the survivors. The sweep resolved restrictions without
 361            // going through their parked keys, so every entry in there is now suspect: a
 362            // resolved restriction would linger, and a survivor may be waiting on a different
 363            // edge than when it was parked.
 0364            _pendingByWay.Clear();
 0365            _pending.Clear();
 0366            foreach (var restriction in _pendingRestrictions)
 0367            {
 0368                this.ParkNoLock(restriction);
 0369            }
 370
 0371            Volatile.Write(ref _pendingRestrictionCount, _pendingRestrictions.Count);
 0372        }
 0373    }
 374
 375    /// <summary>
 376    /// How many restrictions are still unresolved.
 377    /// </summary>
 378    public int PendingRestrictionCount
 379    {
 380        get
 70381        {
 70382            lock (_pendingRestrictionsLock)
 70383            {
 70384                return _pendingRestrictions.Count;
 385            }
 70386        }
 387    }
 388}