[lworld] Flattening of nullable elements of classes similar to j.l.Long

XMLWordPrintable

    • Type: Enhancement
    • Resolution: Unresolved
    • Priority: P4
    • repo-valhalla
    • Affects Version/s: repo-valhalla
    • Component/s: hotspot

      My assumption is that a Long can be flattened just fine. A store of a not-null Long into a nullable Long field will then be:

          while (true) {
              int n = field.null_marker;
              if ((n & 1) != 0) {
                  store field.value;
                  break;
              }
              if (n != 0) {
                  continue;
              }
              if (cmpxchg(&field.null_marker, 0, 0b10)) {
                  store field.value;
                  release_fence; // can probably be a store_store_fence
                  field.null_marker = 1;
                  break;
              }
          }

      and the store of a null into that field will be:

          while (true) {
              int n = field.null_marker;
              if ((n & 1) == 0) {
                   break;
              }
              if (n != 1) {
                  continue;
              }
              if (cmpxchg(&field.null_marker, 1, 0)) {
                  break;
              }
          }

      While, a load can be executed as:

          load (field.null_marker & 1);
          acquire_fence; // can probably be a load_load_fence
          load field.value;

      The general idea is that, all stores that try to write into the null marker must serialize.

      What we need to prove is that, given n concurrent stores, then:

      1. The final state of the memory must be one of the executed stores:
      Consider the stores into the null marker:
      - If the last state of the null marker is 0, then the field is null
      - If the last state of the null marker is 1, then the field is non-null. In this case, only the threads that store non-null Long objects touch the memory of value. One of which would be the last state of the memory here. And it is as if we have a single non-null store that is the last state.

      Note that the fences are irrelevant for these conditions.

      2. Given a concurrent load, then it must either observe the initial state, or 1 of the stores that is executing, and the store observed must not happen before another store, which in turn, happens before the load:

      - If it observes the null marker being 0, then it observes field being null. In this case, only the null marker is relevant, and it is trivially atomic.
      - If it observes the null marker being 1, then it observes field being non-null. In this case, we must prove that:
        + It cannot observe the original value of the payload if the original value of the null marker is 0. Since the load observes the null marker being 1, it must observe a store into the null marker by 1 of the concurrent store. As a result, it must not observe the original value of payload, since the store to payload happens before the store to the null marker, which happens before the load from the null marker, which happens before the load from the payload.
        + It cannot observe an overwritten store. That is, if a store x happens before y, which happens before a load a, then a cannot observe x. It can be seen that y must be a store of null, or it had overwritten the payload value written by x. Furthermore, a must observe the null marker stored by a concurrent store z, since the null marker has been overwritten by y. As a result, since y and z both write to the null marker, they must serialize. And since a observes the null marker written by z, z must happen after y. In which case, x happens before z, so a cannot observe the payload written by x. In conclusion, it cannot be the case that a load observes a store that should be overwritten.

      As a result, we can see that in any case, the field accesses act as if they are atomic.

            Assignee:
            Quan Anh Mai
            Reporter:
            Quan Anh Mai
            Votes:
            0 Vote for this issue
            Watchers:
            8 Start watching this issue

              Created:
              Updated: