Possible NPE in MapNodes#put

[c-yeung]

There appears to be a null pointer exception that occurs at this line https://github.com/lacuna/bifurcan/blob/7898040044e29ec661146adb059b919091e58726/src/io/lacuna/bifurcan/nodes/MapNodes.java#L195

The rest of the NPE stacktrace

! java.lang.NullPointerException: null
! at io.lacuna.bifurcan.nodes.MapNodes$Node.put(MapNodes.java:193) ~[bifurcan-0.1.0.jar:na]
! at io.lacuna.bifurcan.Map.put(Map.java:139) ~[bifurcan-0.1.0.jar:na]
! at io.lacuna.bifurcan.Map.put(Map.java:135) ~[bifurcan-0.1.0.jar:na]
! at io.lacuna.bifurcan.Map.put(Map.java:130) ~[bifurcan-0.1.0.jar:na]
! at io.lacuna.bifurcan.Map.put(Map.java:24) ~[bifurcan-0.1.0.jar:na]

I see that my project is using an older version of Bifurcan, but judging from my cursory read of the MapNodes implementation, it seems the NPE is still possible?

I suspect the NPE behavior is also non-deterministic. In my testing environment, I had four separate processes populating bifurcan.Map with data from the same source, but only one resulted in the NPE mentioned above.

Unfortunately, I don't have more precise reproduction steps for you. But will update here if I end up finding a test that results in the NPE.

[ztellman]

That error implies that the bitmask and entries in the node are out of sync, which is worrisome. The code there hasn't changed in quite some time, so it's unlikely it's been fixed in a subsequent release. Can you provide any further details about your use of the map? Are you only adding entries, or are you also removing them? Are you using linear() at any point in your mutations?

[c-yeung]

Yes, let me provide some more details. I am only adding new entries, never removing. Here's a test case that roughly mirrors the order of operations that's happening in my project

  @Test
  public void test() {
    IMap<MyKey, MyValue> map = new Map<>();
    IMap<MyKey, MyValue> forked = map.forked();
    IMap<MyKey, MyValue> linear = forked.linear();

    // perform roughly ~250,000 put's. NPE is thrown here by one of the put operations.
    // The put calls are executed in parallel threads from a ForkJoinPool 
    // key is never null but value can be null. 
    linear.put(key, value);

    // never gets to this line when NPE occurs but including this for completeness
    IMap<MyKey, MyValue> result = linear.forked();
  }

[c-yeung]

error implies that the bitmask and entries in the node are out of sync

Could this be happening because my map edits are multi-threaded?

[ztellman]

Yes, linear maps are just like normal Java maps, they're not thread-safe. There are a few ways you could safely accomplish this:

• Wrap a forked map in an AtomicReference and have each thread use updateAndGet on that reference. If there's ~10us of computation between each put, there shouldn't be much contention.
• Have each thread use its own linear map, and then combine them together with merge when they're all done.
• Just wrap a synchronized around the code accessing the map in each thread.
• Use a ConcurrentHashMap instead.

Happy to provide more details about the first two approaches if you have any questions, but for now I'm going to close the issue.

[c-yeung]

Ah, classic case of user error then. Thank you for your input.