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

1. repo owner

I can't reproduce this, I get:

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


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. reporter

I thought so, otherwise it would not have made it into the release. Investigating...

3. reporter

Culprit found, leftover line in gaprc:

SemigroupsOptionsRec.hashlen:=19;


I reckon hashlen now is a record.

4. repo owner

Aha, but I think this should remain open. The package should fail because of the values in SemigroupsOptionsRec. I'll reopen this.

5. repo owner
• changed status to open

Reopening, as the value in SemigroupsOptionsRec should not cause a seg fault!

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)

This must be a GAP bug though, because GAP should not ever segfault executing normal code.

6. repo owner

Setting:

SemigroupsOptionsRec.hashlen := 19;
Test("pkg/semigroups/tst/ideals.tst");


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.

7. 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.

8. 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;
false


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).

9. repo owner
• removed milestone

Removing milestone: 2.2.1 (automated comment)