[MAHOUT-1890] Infinite loop in OpenLongObjectHashMap

• Type: Bug
• Status: Resolved
• Priority: Major
• Resolution: Duplicate
• Affects Version/s: 1.0.0

Environment

java version "1.8.0_66"
Java(TM) SE Runtime Environment (build 1.8.0_66-b17)
Java HotSpot(TM) 64-Bit Server VM (build 25.66-b17, mixed mode)

• Assignee: Unassigned
• Reporter: Michael M.
• Created: 21/Oct/16 19:16
• Updated: 31/Jan/24 22:15
• Resolved: 21/Oct/16 19:31

Description

It seems that OpenLongObjectHashMap<> (org.apache.mahout:mahout-collections:1.0) can enter a state where containsKey (indexOfKey) ends up in an infinite loop, stuck in this loop:

OpenLongObjectHashMap.java

    while (state[i] != FREE && (state[i] == REMOVED || table[i] != key)) {
      i -= decrement;
      //hashCollisions++;
      if (i < 0) {
        i += length;
      }
    }

I haven't identified a minimum set of operations necessary to reach this state, but I have generated a (fairly large) test that achieves it:

TestOpenLongObjectHashMap.java

import java.util.Arrays;
import java.util.List;
import java.util.function.Consumer;
import org.apache.mahout.math.map.OpenLongObjectHashMap;
import org.junit.Test;

public class TestOpenLongObjectHashMap {

    private static final List<Consumer<OpenLongObjectHashMap<Long>>> transcript =
            Arrays.asList(add(66546), add(66847), add(71319), del(71319), add(80177), del(80177), add(88428),
                          add(88861), add(92709), del(92709), add(94392), del(94392), add(99506), del(99506),
                          add(104232), add(104968), del(104232), del(104968), add(111042), del(111042), add(123271),
                          del(123271), add(130887), del(66847), add(131387), add(131537), add(131569), del(131537),
                          add(135253), del(135253), add(138781), del(138781), add(141689), del(141689), add(144224),
                          del(144224), add(147237), del(147237), add(152945), add(153646), del(152945), add(154915),
                          del(154915), add(155621), del(155621), add(158464), add(158724), del(158724), del(158464),
                          add(174017), del(174017), add(176818), del(176818), add(178344), add(178716), del(178344),
                          add(178956), del(178956), del(178716), add(181714), del(181714), add(188533), del(188533),
                          add(189152), del(189152), del(131569), add(193603), add(193614), add(193632), del(193614),
                          add(193650), add(193661), add(193662), del(193662), add(193691), add(193761), del(193661),
                          del(193761), add(193801), add(193812), del(193650), del(131387), del(193603), add(193837),
                          del(193837), add(194160), add(194175), del(194160), add(194224), del(194175), add(195507),
                          add(195617), add(195838), add(196272), add(196402), add(196410), del(196272), del(195507),
                          add(196426), add(196427), del(193691), add(196439), add(196440), del(195838), add(196449),
                          del(196426), add(196460), add(196634), del(196449), del(196402), del(196439), del(196440),
                          add(197250), add(197482), add(197531), del(193632), add(197983), del(197250), del(197983),
                          del(196634), add(199455), add(199648), add(200356), add(200397), add(200711), del(200356),
                          del(199648), add(201133), del(200711), add(201209), del(201209), del(196410), del(200397),
                          add(205160), del(205160), del(197531), del(196427), add(207533), add(207546), del(196460),
                          del(197482), add(207555), add(207556), add(207660), add(207820), del(207555), del(207556),
                          del(207660), add(208887), add(208944), del(208944), add(210976), del(210976), add(212301),
                          del(208887), add(213198), del(207546), del(213198), add(213321), del(212301), add(213402),
                          add(214597), del(214597), add(224378), add(225915), add(229080), del(213402), add(229346),
                          del(225915), del(224378), add(231030), add(231151), add(231373), del(231030), del(231373),
                          del(229080), add(232821), del(232821), add(233121), add(233146), del(233146), del(233121),
                          add(233947), del(233947), del(229346), add(234011), add(234078), add(234093), del(207820),
                          add(234582), del(207533), add(234590), add(235295), add(235463), add(235815), del(235295),
                          del(234582), del(235815), add(236133), del(236133), del(235463), add(239925), add(239957),
                          del(239957), add(242934), del(242934), add(243629), add(244092), del(234078), del(243629),
                          del(234011), add(244298), add(244413), add(244427), add(244695), del(244092), del(244695),
                          add(245241), del(239925), del(234093), add(247267), del(244298), del(231151), add(247766),
                          add(247772), add(247773), add(247892), del(244413), add(249689), add(249831), del(249831),
                          del(245241), add(253283), del(249689), del(253283), add(254814), del(254814), add(256746),
                          add(258382), del(244427), add(259392), del(256746), del(258382), add(263266), add(266622),
                          add(267835), del(267835), del(266622), add(270727), add(270786), add(271043), del(271043),
                          del(270727), add(274128), del(274128), del(270786), add(276954), del(276954), add(277773),
                          add(277827), del(277773), add(278443), del(278443), del(277827), add(280444), add(280476),
                          add(286186), add(286193), del(286186), add(286205), del(234590), del(201133), del(247267),
                          add(286322), add(286330), del(263266), del(199455), del(286205), add(286376), add(286378),
                          del(280476), del(259392), add(286434), add(286539), add(288067), add(290067), del(290067),
                          add(290809), del(290809), del(288067), add(295950), del(280444), add(296556), add(297276),
                          del(296556), add(297704), add(297907), add(297936), add(297947), add(297956), del(286539),
                          del(297936), add(298595), add(298616), add(298617), add(298643), del(297947), add(298700),
                          add(298701), add(299170), del(299170), del(295950), del(297276), del(286322), add(299644),
                          add(299750), del(286378), add(299751), del(286434), add(299900), add(300040), del(300040),
                          add(300165), del(299900), add(302324), del(302324), add(304371), del(304371), add(306117),
                          del(306117), add(306751), add(307193), del(306751), del(307193), add(307561), del(299644),
                          add(307848), add(307894), del(307894), del(307848), add(308326), del(307561), del(308326),
                          add(311198), del(311198), add(314100), add(314250), add(314454), add(315195), add(315750),
                          add(317668), add(318585), add(319988), add(320038), add(320634), del(320634), add(321154),
                          add(322377), add(322405), del(322405), del(321154), add(322989), add(323488), add(323489),
                          del(323488), del(322989), add(324668), del(323489), add(325651), add(325675), del(325651),
                          add(326387), add(326654), del(326387), del(326654), del(325675), add(327454), add(327844),
                          add(327888), add(328541), del(327844), del(324668), add(329002), add(329792), del(329792),
                          del(329002), add(331123), del(328541), del(331123), add(331626), add(333869), del(333869),
                          add(333939), add(333940), del(333940), del(333939), add(334532), del(334532), del(298616),
                          del(298617), add(336577), add(336578), add(336723), del(317668), add(337556), add(337557),
                          del(336723), add(338153), del(338153), add(339818), add(340153), del(340153), del(339818),
                          add(340253), del(340253), add(341507), del(322377), add(342285), del(341507), del(331626),
                          add(343334), del(300165), add(343339), del(343339), del(343334), add(343453), add(343515),
                          del(343515), add(343958), del(343958), del(195617), add(345163), add(346229), del(346229),
                          del(345163), add(348094), add(348581), add(348958), del(343453), del(348958), del(348581),
                          add(349217), add(349218), del(349218), del(349217), del(342285), add(350002), add(350833),
                          del(350833), add(352160), del(352160), add(354943), del(354943), add(359170), add(359465),
                          add(359480), del(359465), del(359480), del(350002), del(359170), add(363634), del(363634),
                          add(364606), add(367965), del(367965), add(369082), del(369082), del(364606), add(370023),
                          del(370023), add(371449), add(371450), del(371450), del(371449), add(371526), del(371526),
                          add(371834), add(371928), del(371834), del(371928), add(372151), add(372228), add(372276),
                          del(372276), del(372228), add(372364), add(372601), add(372602), del(372151), del(372364),
                          del(372602), add(373037), add(373046), del(373037), add(373288), del(373288), del(373046),
                          del(337557), add(375867), add(376358), add(376582), del(376582), add(378272), del(378272),
                          add(380800), add(381955), add(381958), del(381958), del(372601), add(382278));

    public static Consumer<OpenLongObjectHashMap<Long>> add(final long id) {
        return (map) -> map.put(id, id);
    }

    public static Consumer<OpenLongObjectHashMap<Long>> del(final long id) {
        return (map) -> map.removeKey(id);
    }

    @Test
    public void spinsForever() {
        final OpenLongObjectHashMap<Long> map = new OpenLongObjectHashMap<>();
        for (final Consumer<OpenLongObjectHashMap<Long>> consumer : transcript) {
            consumer.accept(map);
        }
        map.clear();
        map.put(254, 254L);
        map.put(2829, 2829L);
        // We get this far, containsKey ends up spinning in OpenLongObjectHashMap::indexOfKey
        map.containsKey(2866);
    }
}