Segmentation fault when hash length is very small

Issue #116 resolved
Attila Egri-Nagy
created an issue

with GAP stable-4.7, and Semigroups default branch:

gap> SemigroupsOptionsRec.hashlen := 19;;
gap> gens := [                                                              
> PartialPerm( [ 1, 2, 3, 4, 5, 6, 7, 10 ], [ 4, 6, 7, 3, 8, 2, 9, 5 ] ),
> PartialPerm( [ 1, 2, 7, 9 ], [ 5, 6, 4, 3 ] ),
> PartialPerm( [ 1, 2, 6, 7, 8 ], [ 5, 1, 6, 2, 3 ] )];;
gap> S := Semigroup(gens);;
gap> I := SemigroupIdeal(S, [gens[1]^2, gens[2]]);
Segmentation fault: 11

The seg fault is in line 209 of orb.c, and the above code runs ok when Orb is not compiled

Comments (19)

  1. James Mitchell repo owner

    I can't reproduce this, I get:

    gap> Test("pkg/semigroups/tst/ideals.tst");
    Semigroups package: ideals.tst
    elapsed time: 21287ms

    Did you pull and recompile GAP? If you did, then can you give full details of how you produce the seg fault? Even better can you run whatever causes the seg fault in gdb or lldb and show me the output? Thanks!

  2. Markus Pfeiffer

    gap> Test("pkg/semigroups/tst/ideals.tst"); Semigroups package: ideals.tst elapsed time: 23977ms true

    edit: Didn't see that you'd found the problem. I can reproduce the segfault.

    (stable-4.7 from hg, semigroups from hg, dragonflybsd from yesterday)

  3. James Mitchell repo owner


    SemigroupsOptionsRec.hashlen := 19;

    Does indeed cause a segfault. It used to be possible to set SemigroupOptionsRec.hashlen to a number and this was silently converted to a record with the correct components. I must have inadvertently changed this behaviour.

    lldb reports that the error occurs in line 209 of orb.c. So, there are 2 issues:

    1. Semigroups should properly handle SemigroupOptionsRec.hashlen := 19

    2. Orb shouldn't seg fault when the arguments don't make sense. I will try to find a minimal example where I can make orb crash and post it on github.

  4. James Mitchell repo owner

    Just to mention that the options work as I describe above, i.e. it is legal to set SemigroupsOptionsRec.hashlen to an integer. This is then converted into a record with the correct components by the SemigroupOptions function in options.g.

  5. James Mitchell repo owner

    This is a bug in the Orb package, good find Attila! See the example below.

    gap> S := Semigroup(PartialPerm([]));
    <trivial partial perm group on 0 pts with 0 generators>
    gap> o := Orb(GeneratorsOfSemigroup(S), [1], OnSets);
    <open orbit, 1 points>
    gap> Enumerate(o);
    <closed orbit, 2 points>
    gap> AsList(o);
    [ [ 1 ], [  ] ]
    gap> [] in o;

    There are 2 places in the code for ideals where x in o is written where o is an orbit and x is an element of o. If these are changed to HTValue(o!.ht, x) <> fail, then the seg fault in the example above disappears. The problem is that the family of [] and the elements family of o are incompatible (since o is a collection of collections of cyclotomics) and [] is in ListsFamily. So, the \in method for IsObject, IsOrbit and IsHashOrbitRep and IsDenseList which should be applied is not, since:

    #I  Method 2: ``in: for wrong family relation'', value: 1*SUM_FLAGS+2

    Somehow the orbit object is corrupted by the fact that it contains [] twice (because of the incorrect [] in o returning false).

  6. Log in to comment