90da03 add generic cycle detection

Authored and Committed by Philipp Rudo 2 years ago
    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>
    
        
file modified
+2 -0