Add helper classes to for managing shared buffers.

mojo/services/media/common/cpp/fifo_allocator.cc

Index: mojo/services/media/common/cpp/fifo_allocator.cc
diff --git a/mojo/services/media/common/cpp/fifo_allocator.cc b/mojo/services/media/common/cpp/fifo_allocator.cc
new file mode 100644
index 0000000000000000000000000000000000000000..adf6263e1ad3916693f2947e95dcf1c79e73e525
--- /dev/null
+++ b/mojo/services/media/common/cpp/fifo_allocator.cc
@@ -0,0 +1,220 @@
+// Copyright 2015 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <cassert>
+
+#include "mojo/services/media/common/cpp/fifo_allocator.h"
+
+namespace mojo {
+namespace media {
+
+FifoAllocator::FifoAllocator(uint64_t size) : front_(nullptr), free_(nullptr) {
+  // front_ and free_ need to be set to nullptr before calling reset.

[johngro, 2015/12/05 00:45:55]

MOJO_DCHECK(size < kNullOffset);

[dalesat, 2015/12/07 18:30:20]

Done.

+  Reset(size);
+}
+
+FifoAllocator::~FifoAllocator() {
+  assert(front_ == back_);

[johngro, 2015/12/05 00:45:54]

its probably better to use MOJO_DCHECK here instead of assert.  The main
advantages are..

+ when the asserts drop out of the code in a release build, MOJO_DCHECK will
keep the compiler from complaining about any variables which would be computed
but unused if not for the DCHECK.  There are a few instances of this in the
file, and they currently break a release build.
+ MOJO_DCHECK will go to the logging infrastructure instead of dumping to
stdout.  As time goes on, this will become more and more important.
+ Any other standard context we want to dump when we fail an assert can be added
to DCHECK over time, and may or may not be present in the <cassert>
implementation of assert.

here and below.

[dalesat, 2015/12/07 18:30:20]

Done.

+  DeleteFrontToBack(front_);
+  DeleteFrontToBack(free_);
+}
+
+void FifoAllocator::Reset(uint64_t size) {
+  DeleteFrontToBack(front_);
+  DeleteFrontToBack(free_);
+  size_ = size;
+  free_ = nullptr;
+  front_ = back_ = active_ = get_free(false, size, 0);
+  active_->prev = nullptr;
+  active_->next = nullptr;
+}
+
+uint64_t FifoAllocator::AllocateRegion(uint64_t size) {
+  assert(size != 0);
+
+  if (active_->size < size) {
+    // The active region is too small. Look for one that's large enough.
+    if (!AdvanceActive(size)) {
+      // No unallocated regions are large enough. Can't do the allocation.
+      return kNullOffset;
+    }
+  }
+
+  if (active_->size == size) {
+    // The active region is exactly the right size. Use it for the allocation.
+    auto result = active_->offset;

[johngro, 2015/12/05 00:45:54]

Generally, "auto" is supposed to be used when it reduces the clutter of long
type names and when the type being inferred is obvious from the context.  The
classic example would be an iterator pattern like...

std::set<MyTemplatedClass<horrible, template, argument, list>>::iterator iter =
my_set_.begin();

vs.

auto iter = my_set_.begin();

In this case of "auto" for "uint64_t"... I can figure out that this is needs to
be a uint64_t either by opening the header file and finding out what type
active_ is, then finding the type of active_->offset from that; or by looking at
how result is used later on in this function and assuming that the compiler will
enforce the type safety (and not perform and implicit casts).  Still, I feel
that it would help readability to use the explicit type instead of saying "auto"
here.

OTOH - If the goal here is to maintain flexibility (so that the type of an
offset can be changed without updating all of the code), then adding a using to
the class is probably the better thing to do.  Something like

using MyOffsetType = uint64_t;

or

typedef uint64_t MyOffsetType;

if you want a more old-school style.

[dalesat, 2015/12/07 18:30:20]

Done.

+    active_->allocated = true;
+    if (active_ == back_ && !front_->allocated) {
+      // active_ was the back region and the front region isn't allocted. Make

[johngro, 2015/12/05 00:45:55]

s/allocted/allocated

[dalesat, 2015/12/07 18:30:20]

Done.

+      // the front region the new active region.
+      active_ = front_;
+    } else {
+      // The region after active_ is allocated, so make a zero-sized
+      // placeholder.
+      MakeActivePlaceholder();
+    }
+    return result;
+  }
+
+  // The active region can accommodate this allocation with room left over.
+  // Create a new region (allocated) of the requested size at the front of the
+  // active region, and adjust the active region to reflect the deficit.
+  assert(active_->size > size);
+  auto allocated = get_free(true, size, active_->offset);

[johngro, 2015/12/05 00:45:54]

s/auto/Region*

[dalesat, 2015/12/07 18:30:20]

Done.

+  active_->size -= size;
+  active_->offset += size;
+  insert_before(allocated, active_);
+  return allocated->offset;
+}
+
+void FifoAllocator::ReleaseRegion(uint64_t size, uint64_t offset) {
+  // Start at active_->next. That's usually the region we're looking for.
+  auto released =

[johngro, 2015/12/05 00:45:54]

s/auto/bool

[dalesat, 2015/12/07 18:30:20]

Done.

+      Release(size, offset, active_->next, nullptr) ||
+      Release(size, offset, front_, active_);
+  assert(released);
+}
+
+bool FifoAllocator::Release(
+    uint64_t size,
+    uint64_t offset,
+    Region* begin,
+    Region* end) {

[johngro, 2015/12/05 00:45:55]

MOJO_DCHECK(begin);

[dalesat, 2015/12/07 18:30:20]

Can be nullptr if end is nullptr.
Done.

+  for (Region* region = begin; region != end; region = region->next) {
+    if (region->offset == offset) {
+      assert(region->allocated);
+      assert(region->size == size);
+      region->allocated = false;
+
+      auto prev = region->prev;
+      if (prev != nullptr && !prev->allocated) {
+        // Coalesce wtih the previous region.
+        prev->size += region->size;
+        remove(region);
+        put_free(region);
+        region = prev;
+      }
+
+      auto next = region->next;
+      if (next != nullptr && !next->allocated) {
+        // Coalesce wtih the next region.
+        next->offset = region->offset;
+        next->size += region->size;
+        if (active_ == region) {
+          // This can happen if we coalesced the previous region.
+          active_ = next;
+        }
+        remove(region);
+        put_free(region);
+      }
+
+      return true;
+    }
+  }
+
+  return false;
+}
+
+bool FifoAllocator::AdvanceActive(uint64_t size) {
+  assert(size != 0);
+  return
+      AdvanceActive(size, active_->next, nullptr) ||
+      AdvanceActive(size, front_, active_);
+}
+
+bool FifoAllocator::AdvanceActive(uint64_t size, Region* begin, Region* end) {
+  for (Region* region = begin; region != end; region = region->next) {
+    if (!region->allocated && region->size >= size) {
+      if (active_->size == 0) {
+        // The old active region is zero-sized. Get rid of it.
+        assert(!active_->allocated);
+        remove(active_);

[johngro, 2015/12/05 00:45:55]

put_free(active_);

In general, is there ever a time where we would want to remove a node from the
[front_, back_] list and not return it to the free pool?  Perhaps remove should
just automatically add to the free pool.

[dalesat, 2015/12/07 18:30:20]

Done. I'd rather not put_free in remove, because this is inconsistent with
remove semantics in other containers.

+      }
+      active_ = region;
+      return true;
+    }
+  }
+  return false;
+}
+
+void FifoAllocator::MakeActivePlaceholder() {
+  // If the old active region was at the back of the list, we'll be inserting
+  // at the front, so make the offset zero. We insert at the front, because it's
+  // a bit more efficient and because we don't need to implement insert_after.
+  auto new_active = get_free(
+      false,
+      0,
+      active_ == back_ ? 0 : active_->offset + active_->size);
+
+  assert((active_ == back_) == (active_->next == nullptr));
+  insert_before(new_active, active_ == back_ ? front_ : active_->next);
+  active_ = new_active;
+}
+
+void FifoAllocator::remove(Region* region) {
+  assert(region);
+
+  if (front_ == region) {
+    assert(region->prev == nullptr);
+    front_ = region->next;
+  } else {
+    assert(region->prev);
+    assert(region->prev->next ==region);
+    region->prev->next = region->next;
+  }
+
+  if (back_ == region) {
+    assert(region->next == nullptr);
+    back_ = region->prev;
+  } else {
+    assert(region->next);
+    assert(region->next->prev == region);
+    region->next->prev = region->prev;
+  }
+}
+
+void FifoAllocator::insert_before(Region* region, Region* before_this) {
+  assert(region);
+  assert(before_this);
+
+  region->prev = before_this->prev;
+  before_this->prev = region;
+  region->next = before_this;
+  if (front_ == before_this) {
+    assert(region->prev == nullptr);
+    front_ = region;
+  } else {
+    assert(region->prev);
+    region->prev->next = region;
+  }
+}
+
+FifoAllocator::Region* FifoAllocator::get_free(
+    bool allocated, uint64_t size, uint64_t offset) {
+  assert(size + offset <= size_);

[johngro, 2015/12/05 00:45:54]

in theory, size + offset could wrap and pass this check when it shouldn't. 
suggest

MOJO_DCHECK(size <= size_);
MOJO_DCHECK(offset <= (size_ - size));

instead

[dalesat, 2015/12/07 18:30:20]

Done.

+
+  auto result = free_;
+  if (result == nullptr) {
+    result = new Region();
+  } else {
+    free_ = free_->next;
+  }
+
+  result->allocated = allocated;
+  result->size = size;
+  result->offset = offset;
+
+  return result;
+}
+
+void FifoAllocator::DeleteFrontToBack(Region* region) {
+  while (region != nullptr) {
+    auto to_delete = region;
+    region = region->next;
+    delete to_delete;
+  }
+}
+
+}  // namespace media
+}  // namespace mojo