17
\$\begingroup\$

This is a lock-free Container class. By Container I mean it will hold objects for iteration at a later time. To achieve \$O(1)\$ it returns a token from the put method which you can then use to remove the object. The token is actually the node in which the object has been placed.

It is instantiated with a fixed size and throws an exception if capacity is exhausted. Internally it uses a ring buffer.

It is not intended as a candidate for the Collections toolbox.

Please try to find a way to break it if you can, or point out any areas where you think it might fail under certain situations.

/**
 * Container
 * ---------
 *
 * A lock-free container that offers a close-to O(1) add/remove performance.
 *
 */
public class Container<T> implements Iterable<T> {

  // The capacity of the container.
  final int capacity;
  // The list.
  AtomicReference<Node<T>> head = new AtomicReference<Node<T>>();

  // Constructor
  public Container(int capacity) {
    this.capacity = capacity;
    // Construct the list.
    Node<T> h = new Node<T>();
    Node<T> it = h;
    // One created, now add (capacity - 1) more
    for (int i = 0; i < capacity - 1; i++) {
      // Add it.
      it.next = new Node<T>();
      // Step on to it.
      it = it.next;
    }
    // Make it a ring.
    it.next = h;
    // Install it.
    head.set(h);
  }

  // Empty ... NOT thread safe.
  public void clear() {
    Node<T> it = head.get();
    for (int i = 0; i < capacity; i++) {
      // Trash the element
      it.element = null;
      // Mark it free.
      it.free.set(true);
      it = it.next;
    }
  }

  // Add a new one.
  public Node<T> add(T element) {
    // Get a free node and attach the element.
    return getFree().attach(element);
  }

  // Find the next free element and mark it not free.
  private Node<T> getFree() {
    Node<T> freeNode = head.get();
    int skipped = 0;
    // Stop when we hit the end of the list
    // ... or we successfully transit a node from free to not-free.
    while (skipped < capacity && !freeNode.free.compareAndSet(true, false)) {
      skipped += 1;
      freeNode = freeNode.next;
    }
    if (skipped < capacity) {
      // Put the head as next.
      // Doesn't matter if it fails. That would just mean someone else was doing the same.
      head.set(freeNode.next);
    } else {
      // We hit the end! No more free nodes.
      throw new IllegalStateException("Capacity exhausted.");
    }
    return freeNode;
  }

  // Mark it free.
  public void remove(Node<T> it, T element) {
    // Remove the element first.
    it.detach(element);
    // Mark it as free.
    if (!it.free.compareAndSet(false, true)) {
      throw new IllegalStateException("Freeing a freed node.");
    }
  }

  // The Node class. It is static so needs the <T> repeated.
  public static class Node<T> {

    // The element in the node.
    private T element;
    // Are we free?
    private AtomicBoolean free = new AtomicBoolean(true);
    // The next reference in whatever list I am in.
    private Node<T> next;

    // Construct a node of the list
    private Node() {
      // Start empty.
      element = null;
    }

    // Attach the element.
    public Node<T> attach(T element) {
      // Sanity check.
      if (this.element == null) {
        this.element = element;
      } else {
        throw new IllegalArgumentException("There is already an element attached.");
      }
      // Useful for chaining.
      return this;
    }

    // Detach the element.
    public Node<T> detach(T element) {
      // Sanity check.
      if (this.element == element) {
        this.element = null;
      } else {
        throw new IllegalArgumentException("Removal of wrong element.");
      }
      // Useful for chaining.
      return this;
    }

    public T get () {
      return element;
    }

    @Override
    public String toString() {
      return element != null ? element.toString() : "null";
    }
  }

  // Provides an iterator across all items in the container.
  @Override
  public Iterator<T> iterator() {
    return new UsedNodesIterator<T>(this);
  }

  // Iterates across used nodes.
  private static class UsedNodesIterator<T> implements Iterator<T> {

    // Where next to look for the next used node.
    Node<T> it;
    int limit = 0;
    T next = null;

    public UsedNodesIterator(Container<T> c) {
      // Snapshot the head node at this time.
      it = c.head.get();
      limit = c.capacity;
    }

    @Override
    public boolean hasNext() {
      // Made into a `while` loop to fix issue reported by @Nim
      while (next == null && limit > 0) {
        // Scan to the next non-free node.
        while (limit > 0 && it.free.get() == true) {
          it = it.next;
          // Step down 1.
          limit -= 1;
        }
        if (limit != 0) {
          next = it.element;
        }
      }
      return next != null;
    }

    @Override
    public T next() {
      T n = null;
      if ( hasNext () ) {
        // Give it to them.
        n = next;
        next = null;
        // Step forward.
        it = it.next;
        limit -= 1;
      } else {
        // Not there!!
        throw new NoSuchElementException ();
      }
      return n;
    }

    @Override
    public void remove() {
      throw new UnsupportedOperationException("Not supported.");
    }
  }

}

Having posted this request I now find myself searching aggressively for areas of doubt in the code. Some of those follow but I plan to edit the code and remove these as and when you point me in the right direction.

  1. Should Node<T>.element be volatile? I think perhaps.
  2. Should Node<T>.next be volatile? I think not but I am not sure why.
  3. Have I chosen a good method for the iterator? I picked a counter rather than seeing the head for the second time to ensure I am resilient to an increase/decrease in size of the ring. This has the small downside of having slightly less predictability but it guarantees termination and is only a bit strange under high parallelism.

NB: Container is not intended to be used between a producer and a consumer. It is designed more for keeping a note of which objects have a particular feature in an iterable way. I use it to keep track of threads in the process of calling put on a BlockingQueue (which may of course block) so I can interrupt them if the queue needs to close.

\$\endgroup\$
  • \$\begingroup\$ The original post is here. \$\endgroup\$ – OldCurmudgeon Jun 18 '12 at 13:38
  • \$\begingroup\$ The declaration of stop variable seems to be missing. \$\endgroup\$ – rahul Jun 21 '12 at 16:26
  • \$\begingroup\$ @blufox - my apologies - it should have read limit \$\endgroup\$ – OldCurmudgeon Jun 21 '12 at 18:13
6
+50
\$\begingroup\$

I thought about a comment, but too long, several things I can think of:

  1. This does not guarantee order, i.e. an item is entered into the next free slot, and if there is a fast producer, the order the consumer sees is not guaranteed. Is this intentional?

  2. There is no atomic combined detach/attach operation, this means that for example: Thread A: Attach starts, calls getFree(), which marks the node as not free (and is switched out before the element reference is set) Thread B: is iterating, and hits this node, sees it's not free, so valid node, and returns this, if access to element is done (without a null pointer check), will result in an exception - I guess this is okay(?) Or should you test in your iterator and throw a ConcurrentModification?

I think it's simpler if you maintain an AtomicReference in the node to the element and test that rather than a separate boolean and the reference.

Edit 1:

Looking at this:

  // Doesn't matter if it fails. That would just mean someone else was doing the same.
  head.set(freeNode.next);

Is this necessarily correct? If Thread A sets \$n+1\$ as head at the same time as Thread B setting n as head, and B succeeds - is the ring in a consistent state? I guess the no ordering guarantee means that this doesn't matter too much, but it would violate the \$O(1)\$ claim! ;) In fact, I would question the whole \$O(1)\$ claim, this is at best \$O(1)\$ and at worst \$O(n)\$...

\$\endgroup\$
  • \$\begingroup\$ 1. You are correct - no statement has been made about ordering and there are no guarantees in that respect. All that is guaranteed is that anything that is in the Container throughout iteration time will be offered to the Iterator user. Anything that is added/removed to/from the Container during iteration may or may not be presented to the user. \$\endgroup\$ – OldCurmudgeon Jun 21 '12 at 14:06
  • 1
    \$\begingroup\$ 2. I see your concern. Very good catch. This scenario could then return false from hasNext and thus halt the iteration prematurely. I will fix that. A combined attach/detach would be an interesting detail. Note that the Node class is public and exposes its attach and detach methods so it is possible (encouraged) to replace the object without freeing the slot it occupies if that is desired. \$\endgroup\$ – OldCurmudgeon Jun 21 '12 at 14:07
  • \$\begingroup\$ I hold the AtomicBoolean free in the Node to allow for the above activity (instant detach/attach). I will investigate your idea to see how it affects the algorithm. \$\endgroup\$ – OldCurmudgeon Jun 21 '12 at 14:11
  • \$\begingroup\$ 2. (revisited) On further thought, your scenario may result in null being returned by the next method but will not result in a breach of contract as the iteration will continue because next is a Node not an element. My mistake. BTW - there is an even wider window for this issue because the element can be removed any time between hasNext and next. \$\endgroup\$ – OldCurmudgeon Jun 21 '12 at 14:18
  • 3
    \$\begingroup\$ btw - I think the standard practice with Iterator is that you would call hasNext() and if this is true, call next() to get the element, you should not invoke hasNext() within the call to next(), next() should just return the element. \$\endgroup\$ – Nim Jun 21 '12 at 14:37
0
\$\begingroup\$

If thread A does Container.remove() and then gets interrupted by thread B after the .detach() but before the //Mark it free, and thread B then iterates, it's going to get a ref to an item that's null, which is probably Not What You Want.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the feedback - That was the case in the original code but a recent change triggered by a similar scenario pointed out by @Nim means that the iterator will never return a null value. In your case the null value will be skipped. \$\endgroup\$ – OldCurmudgeon Jun 22 '12 at 8:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.