diff options
| -rw-r--r-- | src/core/managed/Managed.hpp | 28 | ||||
| -rw-r--r-- | src/core/managed/ManagedContainer.hpp | 13 | ||||
| -rw-r--r-- | src/core/managed/Manager.cpp | 161 | ||||
| -rw-r--r-- | src/core/managed/Manager.hpp | 87 |
4 files changed, 274 insertions, 15 deletions
diff --git a/src/core/managed/Managed.hpp b/src/core/managed/Managed.hpp index 04c2f84..eec2fc5 100644 --- a/src/core/managed/Managed.hpp +++ b/src/core/managed/Managed.hpp @@ -64,7 +64,7 @@ public: /** * Virtual destuctor which may be overwritten by child classes. */ - virtual ~Managed(){}; + virtual ~Managed(){ mgr.unmanage(this); }; /** * Returns a reference ot the manager instance which owns this managed @@ -112,6 +112,14 @@ public: } return res; } + + void storeData(const std::string &key, Handle<Managed> h); + + bool hasDataKey(const std::string &key); + + Rooted<Managed> readData(const std::string &key); + + bool deleteData(const std::string &key); }; /** @@ -498,6 +506,24 @@ public: Managed *getOwner() const { return owner; } }; + +inline void Managed::storeData(const std::string &key, Handle<Managed> h) { + mgr.storeData(this, key, h.get()); +} + +inline bool Managed::hasDataKey(const std::string &key) +{ + return mgr.readData(this, key) != nullptr; +} + +inline Rooted<Managed> Managed::readData(const std::string &key) { + return mgr.readData(this, key); +} + +inline bool Managed::deleteData(const std::string &key) { + return mgr.deleteData(this, key); +} + } #endif /* _OUSIA_MANAGED_HPP_ */ diff --git a/src/core/managed/ManagedContainer.hpp b/src/core/managed/ManagedContainer.hpp index 9ff75d5..7b18bcd 100644 --- a/src/core/managed/ManagedContainer.hpp +++ b/src/core/managed/ManagedContainer.hpp @@ -31,8 +31,8 @@ namespace ousia { /** - * Template class which can be used to collect "Owned" refrences to a certain - * type of managed object. Do not use this class directly, use ManagedMap or + * Template class which can be used to collect refrences to a certain type of + * managed objects. Do not use this class directly, use ManagedMap or * ManagedVector instead. This class only provides functionality which is common * to list and map containers (iterators and state). * @@ -40,7 +40,7 @@ namespace ousia { * @param Collection should be a STL container of Owned<T> */ template <class T, class Collection> -class ManagedContainer { +class ManagedContainer : Managed { public: using collection_type = Collection; using value_type = typename collection_type::value_type; @@ -81,7 +81,12 @@ public: * @param owner is the managed object which owns the collection and all * handles to other managed objects stored within. */ - ManagedContainer(Handle<Managed> owner) : owner(owner){}; + ManagedContainer(Handle<Managed> owner) : Managed(owner->getManager), owner(owner){}; + + /** + * Destructor of the ManagedContainer class. + */ + virtual ~ManagedContainer() {}; /* State functions */ size_type size() const noexcept { return c.size(); } diff --git a/src/core/managed/Manager.cpp b/src/core/managed/Manager.cpp index 7b562a8..411c675 100644 --- a/src/core/managed/Manager.cpp +++ b/src/core/managed/Manager.cpp @@ -16,6 +16,8 @@ along with this program. If not, see <http://www.gnu.org/licenses/>. */ +#include <cassert> + #include "Managed.hpp" #include "Manager.hpp" @@ -48,7 +50,7 @@ public: ~ScopedIncrement() { i--; } }; -/* Class ObjectDescriptor */ +/* Class Manager::ObjectDescriptor */ bool Manager::ObjectDescriptor::hasInRef() const { @@ -127,6 +129,8 @@ Manager::~Manager() } } +/* Class Manager: Garbage collection */ + Manager::ObjectDescriptor *Manager::getDescriptor(Managed *o) { if (o) { @@ -145,6 +149,11 @@ void Manager::manage(Managed *o) void Manager::addRef(Managed *tar, Managed *src) { + // Make sure the source and target manager are the same + if (src) { + assert(&tar->getManager() == &src->getManager()); + } + // Fetch the Managed descriptors for the two objects ObjectDescriptor *dTar = getDescriptor(tar); ObjectDescriptor *dSrc = getDescriptor(src); @@ -165,6 +174,11 @@ void Manager::addRef(Managed *tar, Managed *src) void Manager::deleteRef(Managed *tar, Managed *src, bool all) { + // Make sure the source and target manager are the same + if (src) { + assert(&tar->getManager() == &src->getManager()); + } + // Fetch the Managed descriptors for the two objects ObjectDescriptor *dTar = getDescriptor(tar); ObjectDescriptor *dSrc = getDescriptor(src); @@ -177,9 +191,8 @@ void Manager::deleteRef(Managed *tar, Managed *src, bool all) // Decrement the input degree of the input Managed if (dTar && dTar->decrDegree(RefDir::IN, src, all)) { // If the Managed has a zero in degree, it can be safely deleted, - // otherwise - // if it has no root reference, add it to the "marked" set which is - // subject to tracing garbage collection + // otherwise if it has no root reference, add it to the "marked" set + // which is subject to tracing garbage collection if (!dTar->hasInRef()) { deleteObject(tar, dTar); } else if (dTar->rootRefCount == 0) { @@ -205,15 +218,17 @@ void Manager::deleteObject(Managed *o, ObjectDescriptor *descr) } // Increment the recursion depth counter. The "deleteRef" function called - // below - // may descend further into this function and the actual deletion should be - // done in a single step. + // below may descend further into this function and the actual deletion + // should be done in a single step. { ScopedIncrement incr{deletionRecursionDepth}; // Add the Managed to the "deleted" set deleted.insert(o); + // Remove the data store entry + store.erase(o); + // Remove all output references of this Managed while (!descr->refOut.empty()) { deleteRef(descr->refOut.begin()->first, o, true); @@ -329,5 +344,137 @@ void Manager::sweep() purgeDeleted(); } } + +/* Class Manager: Attached data */ + +void Manager::storeData(Managed *ref, const std::string &key, Managed *data) +{ + // Add the new reference from the reference object to the data object + addRef(data, ref); + + // Make sure a data map for the given reference object exists + auto &map = store.emplace(ref, std::map<std::string, Managed *>{}).first->second; + + // Insert the given data for the key, decrement the references if + auto it = map.find(key); + if (it == map.end()) { + map.insert(it, std::make_pair(key, data)); + } else { + // Do nothing if the same data is stored + if (it->second == data) { + return; + } + + // Delete the reference from "ref" to the previously stored element. + deleteRef(it->second, ref); + + // Insert a new reference and add the element to the map + map.insert(map.erase(it), std::make_pair(key, data)); + } +} + +Managed *Manager::readData(Managed *ref, const std::string &key) const +{ + // Try to find the reference element in the store + auto storeIt = store.find(ref); + if (storeIt != store.end()) { + // Try to find the key in the map for the element + auto &map = storeIt->second; + auto mapIt = map.find(key); + if (mapIt != map.end()) { + return mapIt->second; + } + } + return nullptr; +} + +std::map<std::string, Managed *> Manager::readData(Managed *ref) const +{ + // Try to find the map for the given reference element and return it + auto storeIt = store.find(ref); + if (storeIt != store.end()) { + return storeIt->second; + } + return std::map<std::string, Managed *>{}; +} + +bool Manager::deleteData(Managed *ref, const std::string &key) +{ + // Find the reference element in the store + auto storeIt = store.find(ref); + if (storeIt != store.end()) { + // Delete the key from the data map + auto &map = storeIt->second; + auto mapIt = map.find(key); + if (mapIt != map.end()) { + // Delete the reference from "ref" to the previously stored element + deleteRef(mapIt->second, ref); + + // Remove the element from the list + map.erase(mapIt); + + return true; + } + } + return false; +} + +/* Class Manager: Tagged Memory */ + +void Manager::tagMemoryRegion(void *tag, void *pStart, void *pEnd) +{ + // Convert start and end to integers + uintptr_t s1 = reinterpret_cast<uintptr_t>(pStart); + uintptr_t e1 = reinterpret_cast<uintptr_t>(pEnd); + +#ifndef NDEBUG + // Make sure the same memory region is not tagged multiple times + const auto itStart = tags.lower_bound(s1); + const auto itEnd = tags.upper_bound(e1); + for (auto it = itStart; it != itEnd; it++) { + uintptr_t s2 = it->first; + uintptr_t e2 = it->second.first; + assert(!((s2 >= s1 && s2 < e1) || (e2 >= s1 && e2 < e1))); + } +#endif + + // Insert the new region + tags.emplace(s1, std::make_pair(e1, tag)); +} + +void Manager::untagMemoryRegion(void *pStart, void *pEnd) +{ + // Convert start and end to integers + uintptr_t s1 = reinterpret_cast<uintptr_t>(pStart); + uintptr_t e1 = reinterpret_cast<uintptr_t>(pEnd); + + auto itStart = tags.lower_bound(s1); + auto itEnd = tags.upper_bound(e1); + for (auto it = itStart; it != itEnd;) { + // Copy the data of the element + uintptr_t s2 = it->first; + uintptr_t e2 = it->second.first; + void* tag = it->second.second; + + // Remove the element from the map as we need to modify it + it = tags.erase(it); + if (s1 <= s2 && e1 >= e2) { + // Remove completely covered elements + continue; + } + if (s1 > s2) { + // Insert s1-s2 section + it = tags.emplace(s2, std::make_pair(s1, tag)).first; + } + if (e1 < e2) { + // Insert e1-e2 section + it = tags.emplace(e1, std::make_pair(e2, tag)).first; + } + + // Go to the next element + it++; + } +} + } diff --git a/src/core/managed/Manager.hpp b/src/core/managed/Manager.hpp index 95d08e1..5b08cf4 100644 --- a/src/core/managed/Manager.hpp +++ b/src/core/managed/Manager.hpp @@ -27,8 +27,9 @@ #ifndef _OUSIA_MANAGER_HPP_ #define _OUSIA_MANAGER_HPP_ -#include <cassert> +#include <cstdint> #include <map> +#include <string> #include <unordered_map> #include <unordered_set> #include <vector> @@ -39,6 +40,12 @@ namespace ousia { // Forward declaration class Managed; +/** + * The Manager class implements tracing garbage collection. Garbage Collection + * is implemented as a simple directed reference graph with connected component + * detection. Garbage collection is performed whenever the number of objects + * marked as "probably unreachable" surpasses a certain threshold. + */ class Manager { public: /** @@ -126,7 +133,6 @@ private: */ static constexpr size_t SWEEP_THRESHOLD = 128; -protected: /** * Threshold that defines the minimum number of entries in the "marked" * set until "sweep" is called. @@ -150,6 +156,16 @@ protected: std::unordered_set<Managed *> deleted; /** + * Map storing the data attached to managed objects. + */ + std::unordered_map<Managed *, std::map<std::string, Managed *>> store; + + /** + * Map for storing the tagged memory regions. + */ + std::map<uintptr_t, std::pair<uintptr_t, void*>> tags; + + /** * Recursion depth while performing deletion. This variable is needed * because the deletion of an object may cause further objects to be * deleted. Yet the actual deletion should only be performed at the @@ -207,7 +223,8 @@ public: /** * Registers an object for being managed by the Manager. The Manager now has * the sole responsibility for freeing the managed object. Under no - * circumstances free the object manually, this will result in double frees. + * circumstances free the object manually as long as other Managed objects + * still hold references to it. * * @param o is the object which is registered for being used with the * Manager. @@ -243,6 +260,70 @@ public: * Performs garbage collection. */ void sweep(); + + /** + * Registers some arbitrary data (in form of a Managed object) for the + * given reference Managed object under a certain (string) key. Overrides + * references to existing data for that key. + * + * @param ref is the Managed object for which the data should be stored. + * @param key is the key under which the data should be stored. + * @param data is a reference to Managed object containing the data that + * should be stored. + */ + void storeData(Managed *ref, const std::string &key, Managed *data); + + /** + * Returns the arbitrary data stored for the given reference managed object. + * + * @param ref is the Managed object for which the data should be stored. + * @param key is the key for which the data should be retrieved. + * @return a reference to the associated data with the given key. + */ + Managed *readData(Managed *ref, const std::string &key) const; + + /** + * Returns a const reference to a map containing all keys and the associated + * data objects. + * + * @param ref is the Managed object for which the data should be stored. + * @return a reference to the internal map from keys to managed objects. + */ + std::map<std::string, Managed *> readData(Managed *ref) const; + + /** + * Deletes the data stored for the given object with the given key. + * + * @param ref is the Managed object for which the data should be stored. + * @param key is the key for which the data should be retrieved. + * @return true if data for this key was deleted, false otherwise. + */ + bool deleteData(Managed *ref, const std::string &key); + + /** + * Stores a tag for the given memory region. May not overlap with another + * memory region. + * + * @param tag is user defined data that should be stored. + * @param pStart marks the beginning of the memory region (inclusive), + * @param pEnd is the end of the memory region (not inclusive). + */ + void tagMemoryRegion(void *tag, void *pStart, void *pEnd); + + /** + * Removes the tag from the given memory region. May be a part of a + * previously tagged region. + */ + void untagMemoryRegion(void *pStart, void *pEnd); + + /** + * Returns the tag for the given pointer or nullptr if no tag is set. + * + * @param p is the pointer for which the tag should be queried. + * @return the associated tag or nullptr if p points at a memory region for + * which no tag is set. + */ + void* memoryRegionTag(void *p); }; } |