Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8293567

AbstractSplittableWithBrineGenerator: salt has digits that duplicate the marker

    XMLWordPrintable

Details

    • b17
    • generic
    • generic
    • Verified

    Description

      A DESCRIPTION OF THE PROBLEM :
      The java.util.random package has a SplittableGenerator. Presently core code for these is implemented in:
      ./src/java.base/share/classes/jdk/internal/util/random/RandomSupport.java

      This class has an inner class AbstractSplittableWithBrineGenerator. When creating a stream of generators for the splits method the spliterator is seeded with a salt. This salt is combined with the stream position to create a unique seed for each new generator in the stream.

      The salt is composed of 4-bit digits. The least significant digit has all the bits set and is equal to 15. The seed is created by left shifting the salt a multiple of 4 and bit wise or'ing with the stream position: ((salt << shift) | index) where shift is a multiple of 4 to avoid overlapping bits.

      All indices have the marker digit placed in front of the value. To ensure that large indices do not repeat a seed previously generated with a smaller index and a reduced shift on the salt, the extra characters in the salt should avoid the marker digit. This ensures that the bits above the marker digit cannot match a shifted salt, and duplication is avoided.

      However the routine to generate the salt uses a signed multiply. The method is:

      Spliterator<SplittableGenerator> makeSplitsSpliterator(long index, long fence, SplittableGenerator source)

      This results in the possible generation of 15 in the extra salt digits. This can be solved using an unsigned multiply from JDK 18.



      STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
      This cannot be reproduced by using JDK classes. The stream of generators will appear to be random as the salt is only one component used to seed a new generator. Direct inspection of the salt is not possible through the API.

      The digit generation routine can be extracted to a method that creates a single 4-bit digit from the high part of the multiplication of a random long and the multiplier 15. Paste the following into a JShell instance:

      static void signedMultiply(int size, SplittableRandom rng, int m) {
        int[] c = new int[m + 1];
        while (size-- > 0) {
          long x = rng.nextLong();
          long y = Math.multiplyHigh(x, m) & m;
          c[(int) y]++;
        }
        System.out.println(java.util.Arrays.toString(c));
      }

      static void unsignedMultiply(int size, SplittableRandom rng, int m) {
        int[] c = new int[m + 1];
        while (size-- > 0) {
          long x = rng.nextLong();
          long y = Math.unsignedMultiplyHigh(x, m) & m;
          c[(int) y]++;
        }
        System.out.println(java.util.Arrays.toString(c));
      }

      int size = 100000;
      SplittableRandom rng = new SplittableRandom(125634128718L);
      int m = 15;
      signedMultiply(size, rng, m);
      unsignedMultiply(size, rng, m);


      EXPECTED VERSUS ACTUAL BEHAVIOR :
      EXPECTED -
      The random digit for the salt should be in [0, 15).

      Currently the digit is in [0, 15].

      This can result in duplications as the upper bits in the salt can match a left-shifted salt.

      ACTUAL -
      jshell
      | Welcome to JShell -- Version 19
      | For an introduction type: /help intro

      jshell> static void signedMultiply(int size, SplittableRandom rng, int m) {
         ...> int[] c = new int[m + 1];
         ...> while (size-- > 0) {
         ...> long x = rng.nextLong();
         ...> long y = Math.multiplyHigh(x, m) & m;
         ...> c[(int) y]++;
         ...> }
         ...> System.out.println(java.util.Arrays.toString(c));
         ...> }
         ...>
         ...> static void unsignedMultiply(int size, SplittableRandom rng, int m) {
         ...> int[] c = new int[m + 1];
         ...> while (size-- > 0) {
         ...> long x = rng.nextLong();
         ...> long y = Math.unsignedMultiplyHigh(x, m) & m;
         ...> c[(int) y]++;
         ...> }
         ...> System.out.println(java.util.Arrays.toString(c));
         ...> }
         ...>
         ...> int size = 100000;
         ...> SplittableRandom rng = new SplittableRandom(125634128718L);
         ...> int m = 15;
         ...> signedMultiply(size, rng, m);
         ...> unsignedMultiply(size, rng, m);
      | created method signedMultiply(int,SplittableRandom,int)
      | created method unsignedMultiply(int,SplittableRandom,int)
      size ==> 100000
      rng ==> java.util.SplittableRandom@b1bc7ed
      m ==> 15
      [6697, 6797, 6651, 6591, 6702, 6558, 6671, 3334, 3320, 6726, 6613, 6637, 6584, 6599, 6870, 6650]
      [6679, 6750, 6696, 6604, 6712, 6664, 6621, 6681, 6692, 6588, 6531, 6786, 6693, 6682, 6621, 0]


      ---------- BEGIN SOURCE ----------
      See JShell code
      ---------- END SOURCE ----------

      CUSTOMER SUBMITTED WORKAROUND :
      None.

      Note: The bug is unlikely to result in salt duplications. A stream of generators is likely to be created using a small size as there are few use cases for millions of random generators.


      FREQUENCY : always


      Attachments

        Issue Links

          Activity

            People

              rgiulietti Raffaello Giulietti
              webbuggrp Webbug Group
              Votes:
              0 Vote for this issue
              Watchers:
              5 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved: