add generic cycle detection
Resolves: bz2069200
Upstream: github.com/makedumpfile/makedumpfile.git
Conflicts: None
commit feae3d1754d2b0788ce1f18b0cd4b40098ff52ff
Author: Philipp Rudo <prudo@redhat.com>
Date: Mon Mar 14 17:04:29 2022 +0100
[PATCH v2 1/3] add generic cycle detection
In order to work makedumpfile needs to interpret data read from the
dump. This can cause problems as the data from the dump cannot be
trusted (otherwise the kernel wouldn't have panicked in the first
place). This also means that every loop which stop condition depend on
data read from the dump has a chance to loop forever. Thus add a generic
cycle detection mechanism that allows to detect and handle such
situations appropriately.
For cycle detection use Brent's algorithm [1] as it has constant memory
usage. With this it can also be used in the kdump kernel without the
danger that it runs oom when iterating large data structures.
Furthermore it only depends on some pointer arithmetic. Thus the
performance impact (as long as no cycle was detected) should be
comparatively small.
[1] https://en.wikipedia.org/wiki/Cycle_detection#Brent's_algorithm
Suggested-by: Dave Wysochanski <dwysocha@redhat.com>
Signed-off-by: Philipp Rudo <prudo@redhat.com>
Reviewed-and-tested-by: Dave Wysochanski <dwysocha@redhat.com>
Signed-off-by: Philipp Rudo <prudo@redhat.com>