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

BitSet.valueOf(...) allows bitsets to be created that behave incorrectly.

XMLWordPrintable

    • generic
    • generic

      A DESCRIPTION OF THE PROBLEM :
      All 4 overloaded BitSet.valueOf(...) methods allow the user to load in objects that are too big, leading to the class' wordsInUse field to become too big. This in turn causes the length() method to overflow.
      The largest value that wordsInUse normally can get to is Integer.MAX_VALUE/64 + 1 (we refer to this as MAX_WIU). If wordsInUse is set to a value higher than MAX_WIU, then length() will overflow when doing BITS_PER_WORD * (wordsInUse - 1) + ...
      Alongside the overflow in length(), it also means that a number of optimisations no longer properly work, as these assume wordsInUse only refers to bits accessible to the bitset.

      STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
      This description applies to the valueOf(long[]) method, but similar steps apply for the other methods:
      1) Create an array with a length greater than Integer.MAX_VALUE/64 + 1 (MAX_WIU).
      2) Set at least one bit in this array to 1, in an element at index >= MAX_WIU. (For avoidance of doubt, this is: arr[i] with i >= MAX_WIU.)
      3) Use the BitSet.valueOf(long[]) method.

      EXPECTED VERSUS ACTUAL BEHAVIOR :
      EXPECTED -
      Call length() on the newly created bitset. Provided this method returns a value > 0*, call bitset.get( bitset.length()-1 ). The expected result is that this call will return True, as per length() specification.

      *: It is possible for the length() to overflow to a negative number or to 0. In this case, the .get( .length()-1 ) call is not possible. The "Furthermore" part however does still apply.
      ACTUAL -
      The actual result is that this call will return False.

      Furthermore, while bits were set in the original array, no bits are set to true in the new bitset.

      ---------- BEGIN SOURCE ----------
      int MAX_WIU = Integer.MAX_VALUE/64 + 1;

      // Expected
      long[] okArr = new long[MAX_WIU];
      okArr[ okArr.length-1 ] = 1;
      BitSet okBS = BitSet.valueOf(okArr);
      System.out.println(okBS.length()); // 2147483585
      System.out.println(okBS.get( okBS.length()-1 )); // TRUE

      // Actual
      long[] arr = new long[2*MAX_WIU+1];
      arr[ arr.length-1 ] = 1;
      BitSet bitSet = BitSet.valueOf(arr);
      System.out.println(bitSet.length()); // 1
      System.out.println(bitSet.get( bitSet.length()-1 )); // FALSE

      LongBuffer lb = LongBuffer.wrap(arr);
      BitSet bitSet2 = BitSet.valueOf(lb);
      System.out.println(bitSet2.length()); // 1
      System.out.println(bitSet2.get( bitSet2.length()-1 )); // FALSE

      ByteBuffer bb = ByteBuffer.allocate(arr.length * Long.BYTES);
      bb.asLongBuffer().put(arr);
      BitSet bitSet3 = BitSet.valueOf(bb);
      System.out.println(bitSet3.length()); // 57
      System.out.println(bitSet3.get( bitSet3.length()-1 )); // FALSE

      byte[] barr = new byte[bb.remaining()];
      bb.get(barr);
      BitSet bitSet4 = BitSet.valueOf(barr);
      System.out.println(bitSet4.length()); // 57
      System.out.println(bitSet4.get( bitSet4.length()-1 )); // FALSE
      ---------- END SOURCE ----------

      FREQUENCY : always


            smarks Stuart Marks
            webbuggrp Webbug Group
            Votes:
            0 Vote for this issue
            Watchers:
            5 Start watching this issue

              Created:
              Updated: