ultra summit set segfaults

[jeanluct]

ultra summit set segfaults

[jeanluct]

Some initial checks with valgrind. Make a file bug.in that contains

u
6
2 1 3 2 1 4 3 2 5 4 3 2 1 1 4
foo.txt

Then, after compiling with -g flag (and without -O) in the two Makefiles, run

valgrind --leak-check=yes --track-origins=yes --log-file=valgrind.out ./braiding < bug.in 

Output file valgrind.out:

==20190== Memcheck, a memory error detector
==20190== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==20190== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==20190== Command: ./braiding
==20190== Parent PID: 15179
==20190== 
==20190== Use of uninitialised value of size 8
==20190==    at 0x409D4E: CBraid::Factor<CBraid::ArtinPresentation>::At(int) const (cbraid_implementation.h:494)
==20190==    by 0x4084E3: CBraid::Factor<CBraid::ArtinPresentation>::Flip(int) const (cbraid_implementation.h:665)
==20190==    by 0x412734: Braiding::Returns(CBraid::Braid<CBraid::ArtinPresentation>, CBraid::Factor<CBraid::ArtinPresentation>) (braiding.cpp:1000)
==20190==    by 0x413EFC: Braiding::MinUSS(CBraid::Braid<CBraid::ArtinPresentation>, CBraid::Factor<CBraid::ArtinPresentation>) (braiding.cpp:1163)
==20190==    by 0x414502: Braiding::MinUSS(CBraid::Braid<CBraid::ArtinPresentation>) (braiding.cpp:1213)
==20190==    by 0x414C4A: Braiding::USS(CBraid::Braid<CBraid::ArtinPresentation>) (braiding.cpp:1270)
==20190==    by 0x4057B2: main (braiding_main.cpp:740)
==20190==  Uninitialised value was created by a stack allocation
==20190==    at 0x412635: Braiding::Returns(CBraid::Braid<CBraid::ArtinPresentation>, CBraid::Factor<CBraid::ArtinPresentation>) (braiding.cpp:992)
==20190== 
==20190== Invalid read of size 4
==20190==    at 0x409D4E: CBraid::Factor<CBraid::ArtinPresentation>::At(int) const (cbraid_implementation.h:494)
==20190==    by 0x4084E3: CBraid::Factor<CBraid::ArtinPresentation>::Flip(int) const (cbraid_implementation.h:665)
==20190==    by 0x412734: Braiding::Returns(CBraid::Braid<CBraid::ArtinPresentation>, CBraid::Factor<CBraid::ArtinPresentation>) (braiding.cpp:1000)
==20190==    by 0x413EFC: Braiding::MinUSS(CBraid::Braid<CBraid::ArtinPresentation>, CBraid::Factor<CBraid::ArtinPresentation>) (braiding.cpp:1163)
==20190==    by 0x414502: Braiding::MinUSS(CBraid::Braid<CBraid::ArtinPresentation>) (braiding.cpp:1213)
==20190==    by 0x414C4A: Braiding::USS(CBraid::Braid<CBraid::ArtinPresentation>) (braiding.cpp:1270)
==20190==    by 0x4057B2: main (braiding_main.cpp:740)
==20190==  Address 0x14 is not stack'd, malloc'd or (recently) free'd
==20190== 
==20190== 
==20190== Process terminating with default action of signal 11 (SIGSEGV)
==20190==  Access not within mapped region at address 0x14
==20190==    at 0x409D4E: CBraid::Factor<CBraid::ArtinPresentation>::At(int) const (cbraid_implementation.h:494)
==20190==    by 0x4084E3: CBraid::Factor<CBraid::ArtinPresentation>::Flip(int) const (cbraid_implementation.h:665)
==20190==    by 0x412734: Braiding::Returns(CBraid::Braid<CBraid::ArtinPresentation>, CBraid::Factor<CBraid::ArtinPresentation>) (braiding.cpp:1000)
==20190==    by 0x413EFC: Braiding::MinUSS(CBraid::Braid<CBraid::ArtinPresentation>, CBraid::Factor<CBraid::ArtinPresentation>) (braiding.cpp:1163)
==20190==    by 0x414502: Braiding::MinUSS(CBraid::Braid<CBraid::ArtinPresentation>) (braiding.cpp:1213)
==20190==    by 0x414C4A: Braiding::USS(CBraid::Braid<CBraid::ArtinPresentation>) (braiding.cpp:1270)
==20190==    by 0x4057B2: main (braiding_main.cpp:740)
==20190==  If you believe this happened as a result of a stack
==20190==  overflow in your program's main thread (unlikely but
==20190==  possible), you can try to increase the size of the
==20190==  main thread stack using the --main-stacksize= flag.
==20190==  The main thread stack size used in this run was 8388608.
==20190== 
==20190== HEAP SUMMARY:
==20190==     in use at exit: 934 bytes in 35 blocks
==20190==   total heap usage: 475 allocs, 440 frees, 89,710 bytes allocated
==20190== 
==20190== LEAK SUMMARY:
==20190==    definitely lost: 0 bytes in 0 blocks
==20190==    indirectly lost: 0 bytes in 0 blocks
==20190==      possibly lost: 0 bytes in 0 blocks
==20190==    still reachable: 934 bytes in 35 blocks
==20190==         suppressed: 0 bytes in 0 blocks
==20190== Reachable blocks (those to which a pointer was found) are not shown.
==20190== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==20190== 
==20190== For counts of detected and suppressed errors, rerun with: -v
==20190== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)

[jeanluct]

The problem seems to come from the expressions *B1.FactorList.begin() in braiding.cpp, function Returns (near line 1000). If we print B1, we get (1|0). The first part is its LeftDelta, but the second part is zero. If we add some test code before line 1000:

  std::cerr << B1 << std::endl;
  if (B1.FactorList.empty())
    {
      std::cerr << "FactorList is empty.\n";
    }
  std::cerr << *B1.FactorList.begin() << std::endl;

we get the output

(1|0)
FactorList is empty.
[Segmentation fault (core dumped)

Thus, I think the problem is due to trying to copy an empty FactorList. In particular, a line like

C1=ArtinBraid((*B1.FactorList.begin()).Flip(B1.LeftDelta));

will segfault if FactorList is empty. As far as I can see the goal of *B1.FactorList.begin() is to get the first factor. Then it gets flipped, and a braid is created from that. But here the problem is that there is no FactorList, just a LeftDelta.

[jeanluct]

E-mail de Bert:

j'ai regardé un peu la tresse (pas le code), et je comprends ton analyse. La tresse devient Delta après un cyclage. Du coup, j'ai trouvé un exemple plus simple qui crée le même plantage : 

la tresse à 5 brins  2 1 3 2 1 4 3 2 1 1

Pour une raison qui m'échappe complètement, la tresse à 4 brins  2 1 3 2 1 1  ne provoque pas de plantage. Très étrange.

J'ai un programme de [Juan] qui donne quelques options supplémentaires, comme par exemple "USS conjugacy graph", "minimal conj. graph", "Trajectory under sliding" etc

Je viens d'essayer la tresse qui fait planter ton code sur son programme. Il ne plante pas, mais il fait une autre bêtise : il répond

---------------------------------------------------------------------------------------------------
This file contains the Ultra Summit Set of the braid on 6 strands:

2 1 3 2 1 4 3 2 5 4 3 2 1 1 4 

It has 2 orbits, whose sizes are: 1, 1.

Total size:     2

Thurston type:  Periodic.

Rigidity:       Rigid.

-------------------
 Orbit number 1        Rigid.     Conjugate to itself by Delta.
-------------------

    1:   D


-------------------
 Orbit number 2        Rigid.     Conjugate to the previous orbit by Delta.
-------------------

    1:   D
---------------------------------------------------------------------------------------------------