java.lang.Object
net.i2p.router.transport.udp.SSU2Bitfield
class SSU2Bitfieldextends Object
Container of a long array representing set and unset bits. When a bit higher than the current size + offset is set, the offset shifts up and the lowest set bits are lost.

Also contains methods to convert to/from an ACK block.

Locking: Most methods are synchronized here. Do not call methods with the PeerState2 lock held, chance of deadlock.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static interface 
    SSU2Bitfield.Callback
    Callback interface for bitfield operations.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private final long[]
    bitfield
    Bit storage.
    private int
    highestSet
    Highest set bit before offset, -1 if none.
    (package private) static final int
    MAX_ACK_SPAN
    Largest message-number span (in bits) we will build from a received ACK block.
    private final int
    max_shift
    Maximum shift.
    private final int
    min_shift
    Minimum shift.
    private long
    offset
    Current offset.
    private final int
    size
    Bitfield size.

  • Constructor Summary

    Constructors
    Constructor
    Description
    SSU2Bitfield(int size, long offset)
    Creates a new SSU2Bitfield that represents size unset bits.

  • Method Summary

    Modifier and Type
    Method
    Description
    (package private) static long
    calculateAckSpan(int thru, int acnt, byte[] ranges, int rangeCount)
    Compute the number of message numbers (bits) the bitfield for an ACK block must cover, without allocating one.
    void
    forEachAndNot(SSU2Bitfield bf2, SSU2Bitfield.Callback cb)
    Callback for all bits set in this bitfield but not set in bf2.
    static SSU2Bitfield
    fromACKBlock(long thru, int acnt, byte[] ranges, int rangeCount)
    Rebuild a bitfield from a received ACK block, rejecting a block whose implied span would push the offset below zero or exceed MAX_ACK_SPAN.
    boolean
    get(long bit)
    Return true if the bit is set or false if it is not.
    long
    getHighestSet()
    Return the highest set bit, or -1 if none.
    long
    getOffset()
    The current offset.
    boolean
    set(long bit)
    Mark the given bit as set.
    int
    size()
    The size in bits.
    SSU2Payload.AckBlock
    toAckBlock(int maxRanges)
    Render the set bits as an ACK block, collapsing the top acnt bits into the ACK count and the rest into at most maxRanges ranges.
    String
    toString()
    String representation of this bitfield.
    static String
    toString(long thru, int acnt, byte[] ranges, int rangeCount)
    Pretty print an ACK block.

    Methods inherited from class Object

    clone, equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

  • Field Details

    • MAX_ACK_SPAN

      static final int MAX_ACK_SPAN
      Largest message-number span (in bits) we will build from a received ACK block. A peer's own receive bitfield is 512 bits and shifts up by at most max_shift (4096) before starting over, so a live peer can legitimately describe a span of under 512 + 4096 bits. Anything beyond that is a malformed or hostile block: the span is derived from unvalidated attacker-controlled bytes, so an unchecked value lets a ~1.5KB packet allocate a ~48KB bitfield. The margin here leaves room for implementation differences while capping the allocation at 1KB.
      See Also:

    • bitfield

      private final long[] bitfield
      Bit storage.

    • size

      private final int size
      Bitfield size.

    • max_shift

      private final int max_shift
      Maximum shift.

    • min_shift

      private final int min_shift
      Minimum shift.

    • offset

      private long offset
      Current offset.

    • highestSet

      private int highestSet
      Highest set bit before offset, -1 if none.

  • Constructor Details

    • SSU2Bitfield

      public SSU2Bitfield(int size, long offset)
      Creates a new SSU2Bitfield that represents size unset bits.
      Parameters:
      size - the bitfield width in bits, rounded up to a multiple of 256
      offset - the message number the first bit represents, non-negative

  • Method Details

    • size

      public int size()
      The size in bits.
      Returns:
      the bitfield width in bits

    • getOffset

      public long getOffset()
      The current offset.
      Returns:
      the message number the lowest bit represents

    • set

      public boolean set(long bit) throws IndexOutOfBoundsException
      Mark the given bit as set. When a bit higher than the current size + offset is set, the offset shifts up and the lowest set bits are lost.
      Parameters:
      bit - the absolute message number to set, non-negative
      Returns:
      previous value, true if previously set or unknown
      Throws:
      IndexOutOfBoundsException - if bit is smaller then zero OR if the shift is too big

    • get

      public boolean get(long bit)
      Return true if the bit is set or false if it is not.
      Parameters:
      bit - the absolute message number to test, non-negative
      Returns:
      true if the bit is set, false if unset or already shifted out
      Throws:
      IndexOutOfBoundsException - if bit is smaller then zero

    • getHighestSet

      public long getHighestSet()
      Return the highest set bit, or -1 if none.
      Returns:
      the highest set

    • toAckBlock

      public SSU2Payload.AckBlock toAckBlock(int maxRanges)
      Render the set bits as an ACK block, collapsing the top acnt bits into the ACK count and the rest into at most maxRanges ranges.
      Parameters:
      maxRanges - may be 0
      Returns:
      null if nothing is set

    • calculateAckSpan

      static long calculateAckSpan(int thru, int acnt, byte[] ranges, int rangeCount)
      Compute the number of message numbers (bits) the bitfield for an ACK block must cover, without allocating one.

      Pure and package-visible so the hostile-input case can be tested directly.

      Parameters:
      thru - the highest acked message number
      acnt - number of contiguous acks below thru, 0-255
      ranges - non-null, at least rangeCount * 2 bytes
      rangeCount - number of (nack, ack) range pairs, must be non-zero
      Returns:
      the span in bits, always at least 1
      Throws:
      IndexOutOfBoundsException - if ranges is too short for rangeCount

    • fromACKBlock

      public static SSU2Bitfield fromACKBlock(long thru, int acnt, byte[] ranges, int rangeCount)
      Rebuild a bitfield from a received ACK block, rejecting a block whose implied span would push the offset below zero or exceed MAX_ACK_SPAN.
      Parameters:
      thru - the highest acked message number
      acnt - number of contiguous acks below thru, 0-255
      ranges - may be null
      rangeCount - number of (nack, ack) range pairs
      Returns:
      a bitfield covering every message the block acks
      Throws:
      IllegalArgumentException - if the ranges describe a span larger than MAX_ACK_SPAN

    • forEachAndNot

      public void forEachAndNot(SSU2Bitfield bf2, SSU2Bitfield.Callback cb)
      Callback for all bits set in this bitfield but not set in bf2.

      If this offset is greater than bf2's highest bit set, i.e. this bitfield is completely newer, calls back for all bits in this bitfield.

      If this highest bit set is less than than bf2's offset, i.e. this bitfield is completely older, the callback will not be called.

      Synchs on this and then on bf2.

      Usage: this is the received acks, bf2 is previously acked, callback for each newly acked.

      Parameters:
      bf2 - the previously acknowledged bitfield, updated in place
      cb - called once per message newly acked by this bitfield

    • toString

      public static String toString(long thru, int acnt, byte[] ranges, int rangeCount)
      Pretty print an ACK block.
      Parameters:
      thru - the highest acked message number
      acnt - number of contiguous acks below thru, 0-255
      ranges - may be null
      rangeCount - number of (nack, ack) range pairs
      Returns:
      the block as "ACK 1234-1200 NACK 1199 ACK 1198-1190" style text

    • toString

      public String toString()
      String representation of this bitfield.
      Overrides:
      toString in class Object