Each leg of a via-route supporting u-turns does not need to consider
force-loops. Negative weight checks are sufficient to prevent
incorrect results when waypoints are on the same edge.
* Added approach on the opposite side of the road.
* Additional test and docs coverage for opposite approach
---------
Co-authored-by: Aleksandrs Saveljevs <Aleksandrs.Saveljevs@gmail.com>
* Extract prerelease/build information from package semver
Currently we only extract the major.minor.patch identifiers from
the semver label stored in package.json.
This leads to version information in executables incorrectly
reporting a release version is running on prereleases and special builds.
This commit is a quickfix to extract this information and report it
in version strings.
CMake regex parsing is not sophisticated enough to handle the full semver
regex, so we might need to explore other CMake modules if we want to
strictly parse the label.
Unidirectional traffic signal segments are currently not compressed.
This means traffic signals which are not on turns can be missed and
not applied the correct penalty.
This commit changes this behaviour to correctly handle the graph
compression. Additional tests are added to ensure there is no
regression for other cases (turns, restrictions).
Co-authored-by: Michael Bell <michael@mjjbell.com>
This change adds support for disabling datasets, such that specific
files are not loaded into memory when running OSRM. This enables users
to not pay the memory cost for features they do not intend to use.
Initially, there are two options:
- ROUTE_GEOMETRY, for disabling overview, steps, annotations and waypoints.
- ROUTE_STEPS, for disabling steps only.
Attempts to query features for which the datasets are disabled will
lead to a DisabledDatasetException being returned.
* Ensure required file check in osrm-routed is correctly enforced.
The storage module had a stricter check. This keeps the IOConfig
check in sync.
* Correct HTTP docs to reflect summary output dependency on steps parameter.
There is no summary parameter.
* npm audit fix
Building with GCC 13 failed because for example std::int32_t
was not found. Porting guide [1] suggested to add explicit includes
for <cstdint> if necessary, so did just that.
[1]: https://gcc.gnu.org/gcc-13/porting_to.html
* print tracebacks and line numbers for Lua runtime errors
* revert format changes
* update changelog with lua traceback, #6564
* revert using protected_function for old GetStringListFromFunction and source_function #6564
* add unit test for line numbers in tracebacks, #6564
* apply clang-format (#6564)
* remove unused test helper function, #6564
* suppress leaksanitizer warnings in extract-tests, #6564
When the extractor encounters a lua runtime error, some osmium objects are not freed. In production this doesn't matter because these errors bring down OSRM. In the tests we catch them to ensure they occur, and the leaksanitizer flags them.
This change takes the existing typedefs for weight, duration and
distance, and makes them proper types, using the existing Alias
functionality.
Primarily this is to prevent bugs where the metrics are switched,
but it also adds additional documentation. For example, it now
makes it clear (despite the naming of variables) that most of the
trip algorithm is running on the duration metric.
I've not made any changes to the casts performed between metrics
and numeric types, they now just more explicit.
Currently OSRM parses traffic signal nodes without consideration
for the direction in which the signal applies. This can lead
to duplicated routing penalties, especially when a forward and backward
signal are in close proximity on a way.
This commit adds support for directed signals to the extraction and
graph creation. Signal penalties are only applied in the direction
specified by the OSM tag.
We add the assignment of traffic directions to the lua scripts,
maintaining backwards compatibility with the existing boolean
traffic states.
As part of the changes to the internal structures used for tracking
traffic signals during extraction, we stop serialising/deserialising
signals to the `.osrm` file. The traffic signals are only used by
`osrm-extract` so whilst this is a data format change, it will not
break any existing user processes.
This PR improves routing results by adding support for snapping to
multiple ways at input locations.
This means all edges at the snapped location can act as source/target
candidates for routing search, ensuring we always find the best route,
and not the one dependent on the edge selected.
This change unblocks the osrm-extract debug build, which is
currently failing on a maneuver override assertion.
The processing of maneuver overrides currently has three issues
- It assumes the via node(s) can't be compressed (the failing assertion)
- It can't handle via-paths containing incompressible nodes
- It doesn't interop with turn restriction on the same path
Turn restrictions and maneuver overrides both use the same
from-via-to path representation.
Therefore, we can fix these issues by consolidating their
structures and reusing the path representation for
turn restrictions, which already is robust to the above
issues.
This also simplifies some of the codebase by removing maneuver
override specific path processing.
There are ~100 maneuver overrides in the OSM database, so the
impact on processing and routing will be minimal.
Currently route results are annotated with additional path information,
such as geometries, turn-by-turn steps and other metadata.
These annotations are generated if they are not requested or returned
in the response.
Datasets needed to generate these annotations are loaded and available
to the OSRM process even when unused.
This commit is a first step towards making the loading of these datasets
optional. We refactor the code so that route annotations are only
generated if explicitly requested and needed in the response.
Specifically, we change the following annotations to be lazily generated:
- Turn-by-turn steps
- Route Overview geometry
- Route segment metadata
For example. a /route/v1 request with
steps=false&overview=false&annotations=false
would no longer call the following data facade methods:
- GetOSMNodeIDOfNode
- GetTurnInstructionForEdgeID
- GetNameIndex
- GetNameForID
- GetRefForID
- GetTurnInstructionForEdgeID
- GetClassData
- IsLeftHandDriving
- GetTravelMode
- IsSegregated
- PreTurnBearing
- PostTurnBearing
- HasLaneData
- GetLaneData
- GetEntryClass
Requests that include segment metadata and/or overview geometry
but not turn-by-turn instructions will also benefit from this,
although there is some interdependency with the step instructions
- a call to GetTurnInstructionForEdgeID is still required.
Requests for OSM annotations will understandably still need to
call GetOSMNodeIDOfNode.
Making these changes unlocks the optional loading of data contained in
the following OSRM files:
- osrm.names
- osrm.icd
- osrm.nbg_nodes (partial)
- osrm.ebg_nodes (partial)
- osrm.edges
The internal representation of turn restrictions expects only one
`from` way and only one `to` way.
`no_entry` and `no_exit` turn restrictions can have multiple `from` and
`to` ways respectively. This means they are not fully supported by
OSRM's restriction parser.
We complete support for these turn restriction types by parsing all
ways and converting a valid restriction with multiple `from`/`to` members
into multiple internal restrictions.
The data facade interface contains numerous methods for looking up
datapoints by identifiers.
Many of the parameters use the NodeID or EdgeID types. However, these two
identifier types are used for representing three different contexts:
1. Node-based graph edges and nodes
2. Edge-based graph edges and nodes
3. Packed geometries
Consider the use of identifier parameters in these examples:
---
GetWeightPenaltyForEdgeID(const EdgeID id) <- edge-based edge
GetUncompressedForwardWeights(const EdgeID id) <- packed geometry
IsLeftHandDriving(const NodeID id) <- edge-based node
GetBearingClass(const NodeID node) <- node-based node
---
This mixing of contexts within the same interface makes it
difficult to understand the relationships and dependencies between
the OSRM datasets.
For 1. and 2. we continue to use the NodeID and EdgeID types, but
change the interface parameter names to identify them as
edge-based or node-based graph properties.
For 3. we define a new type definition, PackedGeometryID.
These changes are to aid with readability. A next step would be
to strongly type these definitions, leveraging the Alias template
already used for OSM identifiers.
- Fix typo in util function name for_each_indexed.
- Use the overloaded functions for_each_indexed and for_each_pair
with a container argument where possible to improve readability.
* Add missing profile name to library extract test.
* Support both tzid and TZID properties on timezone geometry. Improve validation of timezone polygons.
* Missing tzid property wasn't a geojson validation issue, shouldn't have been tested there.
* Use filesystem glob to loop over all test executables so we don't miss any in the future.
Co-authored-by: Michael Bell <michael@mjjbell.com>
A request to osrm-routed can be assigned to a thread which
is currently busy processing another request, even when there
are other threads/cores available. This unnecessarily delays
the response, and can make requests appear to hang when
awaiting CPU intensive requests to finish.
The issue looks like a bug in Boost.Asio multithreaded
networking stack.
osrm-routed server implementation is
heavily influenced by the HTTP server 3 example in the
Boost.Asio docs. By upgrading to Boost 1.70 and updating the
server connections to match the example provided in the 1.70
release, the problem is resolved.
The diff of the changes to the Boost.Asio stack are
vast, so it's difficult to identify the exact cause. However
the implementation change is to push the strand of execution
into the socket (and timer) objects, which suggests it could
fix the type of threading issue we are observing.
Each MLD cell has source and destination nodes.
MLD is keeping a |source| x |destination| sized table
for various metrics (distances, durations, etc) from each
source to all destinations in a cell.
It stores all of the values for a metric in one large array, with
an offset for each cell to find its values. The offset is currently
limited to 32 bit values, which overflows on very large graphs
(e.g. Planet OSM).
We fix this by changing the offsets to be uint64_t types.
The generation of level masks for compactly storing partition cells
supports sizes that can be stored in 64 bits.
The current implementation fails if the total bit sum is 64 bits
exactly. A bit shift mechanism is used that is undefined when the
shift size is equal to the bit size of the underlying type. This
generates an incorrect mask value.
We fix this by adding a special case for a 64 bit offset. Given this
code is called at most |level| times, there will be no effect on
performance. We also update the assertions to reflect 64 bit masks
are now supported.
osrm-routed does not immediately clean up a keep-alive connection
when the client closes it. Instead it waits for five seconds
of inactivity before removing.
Given a setup with low file limits and clients opening and
closing a lot of keep-alive connections, it's possible for
osrm-routed to run out of file descriptors whilst it waits for
the clean-up to trigger.
Furthermore, this causes the connection acceptor loop to exit.
Even after the old connections are cleaned up, new ones
will not be created. Any new requests will block until the
server is restarted.
This commit improves the situation by:
- Immediately closing connections on error. This includes EOF errors
indicating that the client has closed the connection. This releases
resources early (including the open file) and doesn't wait for the
timer.
- Log when the acceptor loop exits. Whilst this means the behaviour
can still occur for reasons other than too many open files,
we will at least have visibility of the cause and can investigate further.
OSM node 2^33 was created in early April 2021. This and all
subsequently created IDs will be overflowing OSRM node storage
which only support 33 bit IDs.
Bump the number of bits to 34 to double node ID capacity. This
is a breaking change to the data format as it alters the layout
of .osrm.nbg_nodes.
Removes the breaking libosrm API change by adding the old interface to
the new. This does not introduce any new breaks.
The downside of this is that it allows for multiple ways to
return JSON responses.
