Lazy graph structure caching and concurrency

Question

I am seeing some strange NPEs and have found out that this is a concurrency issue. I'm using code similar to the following:

class Manager {
  private final ConcurrentMap<String, Value> map = new ConcurrentHashMap<>();

  public Value get(String key) {
    Value v = map.get(key);
    if (v == null) {
      new Value(key, this);
      v = map.get(key);
    }
    return v;
  }

  public void doIt(String key) {
    get(key).doIt();
  }

  void register(String key, Value v) {
    map.put(key, v);
  }
}

class Value {
  private final Value[] values;
  private final SubValue v;

  Value(String key, Manager m) {
    m.register(key, this);

    // Initialize some values, this is where a cycle can be introduced
    // This is just some sample code, the gist is, we call Manager.get
    this.vs = new Value[]{ m.get("some-other-key") };
    // Other code ...

    this.v = new SubValue(m);
  }

  public void doIt() {
    this.v.doIt(); // <--- NPE here. v is null sometimes
  }
}

When I call Manager.doIt, I sometimes get an NPE because Value.v is null. As far as I understand the happens-before relationships, it might be possible, that when Manager.get is called concurrently and when there is no entry yet for a key, that I can get back a not yet fully initialized Value.

I'm registering objects in the constructor of Value because the object graph between Value objects can have cycles and without this, I would get a stackoverflow exception.

The question now is, how do I ensure in doIt that the Value and all connected values are fully initialized? I'm thinking about doing some kind of double checked locking in Manager.get but I'm not sure how to solve this best. Something like this:

  public Value get(String key) {
    Value v = map.get(key);
    if (v == null) {
      synchronized(map) {
        v = map.get(key);
        if (v == null) {
          v = new Value(key, this);
        }
      }
    }
    return v;
  }

Has anyone a better idea about how to solve this or sees a concurrency issue with that code?

While I am still figuring out the rest of the program, double-checked locking suffers from memory visibility problems itself. — Prashant Pandey, Oct 07 '20 at 17:27
The problem here is not memory visibility. Inside V's constructor, you're making this reference escape even before the object is properly constructed. — Prashant Pandey, Oct 07 '20 at 17:50
as a side note, your entire _get_ method is not thread safe, by any means. Look into `computeIfAbsent` and carefully read it's documentation. — Eugene, Oct 08 '20 at 02:09

Prashant Pandey · Answer 1 · 2020-10-07T20:06:36.003

1

The problem here is that you're making this escape in the constructor.

class Value {
  private final Value[] values;
  private final SubValue v;

  Value(String key, Manager m) {
    m.register(key, this); <--- (this is not properly constructed)

    // Initialize some values, this is where a cycle can be introduced
    // This is just some sample code, the gist is, we call Manager.get
    this.vs = new Value[]{ m.get("some-other-key") };
    // Other code ...

    this.v = new SubValue(m);
  }

  public void doIt() {
    this.v.doIt(); // <--- NPE here. v is null sometimes
  }
}

Now if some thread calls doIt on a key that has an improperly constructed object against it in the map, you might get an NPE as the Subvalue v for that object might not have been initialised.

The code has another issue. Manager.get() is a compound action, and should be encapsulated in a synchronised block. If one thread observes a null value for a key, by the time it enters the if block, that observation might become stale. Since the map is involved in the compound action, all methods that reference the map should be guarded by the same lock - basically you need to guard get() and register() with the same lock.

edited Oct 07 '20 at 20:06

answered Oct 07 '20 at 17:59

Prashant Pandey

4,332
3
26
44

Since register is only ever called in the constructor of `Value` I think my solution should be safe, because the lock is only acquired when creating the `Value`, or am I missing something? – Christian Beikov Oct 07 '20 at 20:20
1

No, it's not safe. Whey you call register, you're putting an improperly constructed object in the map. There is a race condition - another thread might do a get on that key, get the improperly constructed object, and dereference a field that has not been initialised yet. Making 'this' escape from the constructor is never a good practice, even when it's the last step in the constructor. – Prashant Pandey Oct 07 '20 at 21:28
1+, this is correct. @ChristianBeikov you can think about it rather easy: some thread reads `this` (whatever) you called `register` with _before_ the constructing thread does `this.v = new SubValue(m);` for example. And of course sees a `null`. – Eugene Oct 08 '20 at 02:09
Thanks for the hint, it was a bit late yesterday :D I can't move the register out of the constructor because otherwise I can't have a cyclic object graph. Maybe I should create an intermediate map (visible only to one thread) for initialization and after initialization put all objects in the shared map. What do you think? It's not a problem when some objects are created multiple times when initialized concurrently. – Christian Beikov Oct 08 '20 at 06:51
1

@ChristianBeikov the construction of the cyclic graph does not depend on the `register` method at all. There would be no difference if you just construct all objects of the cyclic graph first and traverse them afterwards to call `register` for each. – Holger Oct 08 '20 at 07:17
@Holger How would I do that? When `Value` constructs values directly instead of looking up an existing instance from the cache, i get a stack overflow A -> B -> A (recursion), the point is, I want `Value` to be immutable. – Christian Beikov Oct 08 '20 at 07:40
1

@ChristianBeikov when object `A` is constructed, it passes itself to the constructor of `B`. As simple as that. Like in [this answer](https://stackoverflow.com/a/57995933/2711488), for example. The `Manager` detour does not improve anything. Unless you consider exposing incomplete objects during construction an improvement. – Holger Oct 08 '20 at 07:47
@ChristianBeikov does this solve your problem? If yes, then please consider accepting it. – Prashant Pandey Oct 08 '20 at 12:50
The thing is, I don't want to use a lock on every access, so your answer is not entirely what I was looking for. I think the only "good" solution would be to have a isolated map and copy over all values after they are fully constructed. This might lead to some duplicate objects, but that's fine for me – Christian Beikov Oct 09 '20 at 10:12
@ChristianBeikov I think the answer pretty much points out the exact mistake that you made. Constructing a solution shouldn't be that difficult now. – Prashant Pandey Oct 12 '20 at 05:45

score 0 · Accepted Answer · answered Oct 09 '20 at 10:17

The solution I went with is the following which is scalable and as far as I can tell, safe:

class Manager {
  private final ConcurrentMap<String, Value> map = new ConcurrentHashMap<>();

  public Value get(String key) {
    Value v = map.get(key);
    if (v == null) {
      Map<String, Value> subMap = new HashMap<>();
      new Value(key, subMap);
      map.putAll(subMap);
      v = map.get(key);
    }
    return v;
  }

  public void doIt(String key) {
    get(key).doIt();
  }
}

class Value {
  private final Value[] values;
  private final SubValue v;

  Value(String key, Map<String, Value> subMap) {
    subMap.put(key, this);

    // Initialize some values, this is where a cycle can be introduced
    // This is just some sample code, the gist is, we call Manager.get
    this.vs = new Value[]{ subMap.containsKey("some-other-key") ? subMap.get("some-other-key") : m.get("some-other-key") };
    // Other code ...

    this.v = new SubValue(m);
  }

  public void doIt() {
    this.v.doIt();
  }
}

Lazy graph structure caching and concurrency

2 Answers2