Improved iterator for persistent memory allocator.

base/metrics/persistent_memory_allocator.h

 // Copyright (c) 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.
 
 #ifndef BASE_METRICS_PERSISTENT_MEMORY_ALLOCATOR_H_
 #define BASE_METRICS_PERSISTENT_MEMORY_ALLOCATOR_H_
 
 #include <stdint.h>
 #include <atomic>
 
@@ skipping 31 matching lines @@
 // segment. In other words, don't share the segment until at least one
 // allocator has been attached to it.
 //
 // Note that memory not in active use is not accessed so it is possible to
 // use virtual memory, including memory-mapped files, as backing storage with
 // the OS "pinning" new (zeroed) physical RAM pages only as they are needed.
 class BASE_EXPORT PersistentMemoryAllocator {
  public:
   typedef uint32_t Reference;
 
-  // Internal state information when iterating over memory allocations.
-  class Iterator {
+  // Iterator for going through all iterable memory records in an allocator.
+  // Like the allocator itself, iterators are lock-free and thread-secure.
+  // That means that multiple threads can share an iterator and the same
+  // reference will not be returned twice.
+  //
+  // Iteration, in general, is tolerant of corrupted memory. It will return
+  // what it can and stop only when corruption forces it to. Bad corruption
+  // could cause the same object to be returned many times but it will
+  // eventually quit.
+  class BASE_EXPORT Iterator {
    public:
-    Iterator() : last(0) {}
+    // Constructs an iterator on a given |allocator|, starting at the beginning.
+    Iterator(const PersistentMemoryAllocator* allocator);

[Ilya Sherman, 2016/03/24 02:03:58]

nit: explicit

[Ilya Sherman, 2016/03/24 02:03:58]

nit: Please document lifetime expectations for this raw pointer.

[bcwhite, 2016/03/24 14:22:34]

Done.

[bcwhite, 2016/03/24 14:22:34]

Done.

 
-    bool operator==(const Iterator& rhs) const { return last == rhs.last; }
-    bool operator!=(const Iterator& rhs) const { return last != rhs.last; }
+    // As above but resuming from the |starting_after| reference. The first call
+    // to GetNext() will return the next object found after that reference. The
+    // reference must be to an "iterable" object; references to non-iterable
+    // objects (those that never had MakeIterable() called for them) will cause
+    // a run-time error.
+    Iterator(const PersistentMemoryAllocator* allocator,
+             Reference starting_after);
 
-    void clear() { last = 0; }
-    bool is_clear() const { return last == 0; }
+    // Gets the next iterable, storing that type in |type_return|. The actual
+    // return value is a reference to the allocation inside the allocator or
+    // zero if there are no more. GetNext() may still be called again at a
+    // later time to retrieve any new allocations that have been added.
+    Reference GetNext(uint32_t* type_return);
+
+    // Similar to above but gets the next iterable of a specific |type_match|.
+    // This should not be mixed with calls to GetNext() because any allocations
+    // skipped here due to a type mis-match will never be returned by later
+    // calls to GetNext() meaning it's possible to completely miss entries.
+    Reference GetNextOfType(uint32_t type_match);
 
    private:
-    friend class PersistentMemoryAllocator;
+    // Weak-pointer to memory allocator being iterated over.
+    const PersistentMemoryAllocator* allocator_;
 
-    Reference last;
-    uint32_t niter;
+    // The last record that was returned.
+    std::atomic<Reference> last_record_;
+
+    // The number of records found; used for detecting loops.
+    std::atomic<uint32_t> record_count_;
+
+    DISALLOW_COPY_AND_ASSIGN(Iterator);
   };
 
   // Returned information about the internal state of the heap.
   struct MemoryInfo {
     size_t total;
     size_t free;
   };
 
   enum : uint32_t {
     kTypeIdAny = 0  // Match any type-id inside GetAsObject().
@@ skipping 126 matching lines @@
   // Once an object is made iterable, its position in iteration can never
   // change; new iterable objects will always be added after it in the series.
   void MakeIterable(Reference ref);
 
   // Get the information about the amount of free space in the allocator. The
   // amount of free space should be treated as approximate due to extras from
   // alignment and metadata. Concurrent allocations from other threads will
   // also make the true amount less than what is reported.
   void GetMemoryInfo(MemoryInfo* meminfo) const;
 
-  // Iterating uses a |state| structure (initialized by CreateIterator) and
-  // returns both the reference to the object as well as the |type_id| of
-  // that object. A zero return value indicates there are currently no more
-  // objects to be found but future attempts can be made without having to
-  // reset the iterator to "first". Creating an iterator |starting_after|
-  // a known iterable object allows "resume" from that point with the next
-  // call to GetNextIterable returning the object after it.
-  void CreateIterator(Iterator* state) const { CreateIterator(state, 0); };
-  void CreateIterator(Iterator* state, Reference starting_after) const;
-  Reference GetNextIterable(Iterator* state, uint32_t* type_id) const;
-
   // If there is some indication that the memory has become corrupted,
   // calling this will attempt to prevent further damage by indicating to
   // all processes that something is not as expected.
   void SetCorrupt() const;
 
   // This can be called to determine if corruption has been detected in the
   // segment, possibly my a malicious actor. Once detected, future allocations
   // will fail and iteration may not locate all objects.
   bool IsCorrupt() const;
 
@@ skipping 123 matching lines @@
 
  private:
   scoped_ptr<MemoryMappedFile> mapped_file_;
 
   DISALLOW_COPY_AND_ASSIGN(FilePersistentMemoryAllocator);
 };
 
 }  // namespace base
 
 #endif  // BASE_METRICS_PERSISTENT_MEMORY_ALLOCATOR_H_