diff --git a/cstore/datapackstore.h b/cstore/datapackstore.h
--- a/cstore/datapackstore.h
+++ b/cstore/datapackstore.h
@@ -15,79 +15,17 @@
 }
 
 #include <ctime>
+#include <memory>
 #include <string>
 #include <unordered_set>
 #include <vector>
 
+#include "cstore/datastore.h"
+#include "cstore/key.h"
 #include "clib/portability/portability.h"
-#include "cstore/key.h"
 
 const clock_t PACK_REFRESH_RATE = 0.1 * CLOCKS_PER_SEC;
 
-class DeltaChainIterator {
-  private:
-    size_t _index;
-  protected:
-    std::vector<delta_chain_t> _chains;
-    DeltaChainIterator() :
-      _index(0) {}
-    virtual delta_chain_t getNextChain(const Key& /*key*/) {
-      return COMPOUND_LITERAL(delta_chain_t) { GET_DELTA_CHAIN_NOT_FOUND };
-    }
-  public:
-    DeltaChainIterator(delta_chain_t chain) :
-      _index(0) {
-      _chains.push_back(chain);
-    }
-
-    virtual ~DeltaChainIterator() {
-      for(std::vector<delta_chain_t>::iterator it = _chains.begin();
-          it != _chains.end();
-          it++) {
-        freedeltachain(*it);
-      }
-    }
-
-    delta_chain_link_t *next() {
-      delta_chain_t *chain = &_chains.back();
-      if (_index >= chain->links_count) {
-        // If we're not at the end, and we have a callback to fetch more, do the
-        // fetch.
-        bool refreshed = false;
-        if (chain->links_count > 0) {
-          delta_chain_link_t *result = &chain->delta_chain_links[_index - 1];
-
-          const uint8_t *deltabasenode = result->deltabase_node;
-          if (memcmp(deltabasenode, NULLID, BIN_NODE_SIZE) != 0) {
-            Key key(result->filename, result->filename_sz,
-                    (const char*)deltabasenode, BIN_NODE_SIZE);
-
-            delta_chain_t newChain = this->getNextChain(key);
-            if (newChain.code == GET_DELTA_CHAIN_OK) {
-              // Do not free the old chain, since the iterator consumer may
-              // still be holding references to it.
-              _chains.push_back(newChain);
-              chain = &_chains.back();
-              _index = 0;
-              refreshed = true;
-            } else {
-              freedeltachain(newChain);
-            }
-          }
-        }
-
-        if (!refreshed) {
-          return NULL;
-        }
-      }
-
-      delta_chain_link_t *result = &chain->delta_chain_links[_index];
-      _index++;
-
-      return result;
-    }
-};
-
 class DatapackStore;
 class DatapackStoreKeyIterator : public KeyIterator {
   private:
@@ -103,7 +41,7 @@
 };
 
 /* Manages access to a directory of datapack files. */
-class DatapackStore {
+class DatapackStore : public DataStore {
   private:
     std::string _path;
     clock_t _lastRefresh;
@@ -122,9 +60,9 @@
 
     DeltaChainIterator getDeltaChain(const Key &key);
 
-    DatapackStoreKeyIterator getMissing(KeyIterator &missing);
+    std::shared_ptr<KeyIterator> getMissing(KeyIterator &missing);
 
-    delta_chain_t getDeltaChainRaw(const Key &key);
+    std::shared_ptr<DeltaChain> getDeltaChainRaw(const Key &key);
 
     bool contains(const Key &key);
 
diff --git a/cstore/datapackstore.cpp b/cstore/datapackstore.cpp
--- a/cstore/datapackstore.cpp
+++ b/cstore/datapackstore.cpp
@@ -101,17 +101,14 @@
 }
 
 DeltaChainIterator DatapackStore::getDeltaChain(const Key &key) {
-  delta_chain_t chain = this->getDeltaChainRaw(key);
-  if (chain.code == GET_DELTA_CHAIN_OK) {
+  std::shared_ptr<DeltaChain> chain = this->getDeltaChainRaw(key);
+  if (chain->code() == GET_DELTA_CHAIN_OK) {
     return DeltaChainIterator(chain);
   }
-
-  freedeltachain(chain);
-
   throw MissingKeyError("unable to find delta chain");
 }
 
-delta_chain_t DatapackStore::getDeltaChainRaw(const Key &key) {
+std::shared_ptr<DeltaChain> DatapackStore::getDeltaChainRaw(const Key &key) {
   for(std::vector<datapack_handle_t*>::iterator it = _packs.begin();
       it != _packs.end();
       it++) {
@@ -128,7 +125,8 @@
       continue;
     }
 
-    return chain;
+    // Pass ownership of chain to DeltaChain
+    return std::make_shared<DeltaChain>(chain);
   }
 
   // Check if there are new packs available
@@ -149,10 +147,11 @@
       continue;
     }
 
-    return chain;
+    // Pass ownership of chain to DeltaChain
+    return std::make_shared<DeltaChain>(chain);
   }
 
-  return COMPOUND_LITERAL(delta_chain_t) { GET_DELTA_CHAIN_NOT_FOUND };
+  return std::make_shared<DeltaChain>(GET_DELTA_CHAIN_NOT_FOUND);
 }
 
 Key *DatapackStoreKeyIterator::next() {
@@ -194,8 +193,8 @@
   return false;
 }
 
-DatapackStoreKeyIterator DatapackStore::getMissing(KeyIterator &missing) {
-  return DatapackStoreKeyIterator(*this, missing);
+std::shared_ptr<KeyIterator> DatapackStore::getMissing(KeyIterator &missing) {
+  return std::make_shared<DatapackStoreKeyIterator>(*this, missing);
 }
 
 std::vector<datapack_handle_t*> DatapackStore::refresh() {
diff --git a/cstore/datastore.h b/cstore/datastore.h
new file mode 100644
--- /dev/null
+++ b/cstore/datastore.h
@@ -0,0 +1,192 @@
+// Copyright (c) 2004-present, Facebook, Inc.
+// All Rights Reserved.
+//
+// This software may be used and distributed according to the terms of the
+// GNU General Public License version 2 or any later version.
+
+// datastore.h - c++ declarations for a data store
+// no-check-code
+
+#ifndef FBHGEXT_DATASTORE_H
+#define FBHGEXT_DATASTORE_H
+
+extern "C" {
+#include "cdatapack/cdatapack.h"
+}
+
+#include <memory>
+#include <vector>
+
+#include "cstore/key.h"
+#include "clib/portability/portability.h"
+
+class DeltaChainLink {
+  private:
+    const char *_filename, *_deltabasefilename;
+    const uint8_t *_node, *_deltabasenode, *_delta;
+    uint16_t _filenamesz;
+    uint64_t _deltasz;
+
+  public:
+    DeltaChainLink(delta_chain_link_t *link) {
+      if (link) {
+        _filename = link->filename;
+        _deltabasefilename = link->filename;
+        _node = link->node;
+        _deltabasenode = link->deltabase_node;
+        _delta = link->delta;
+        _filenamesz = link->filename_sz;
+        _deltasz = link->delta_sz;
+      } else {
+        _filename = NULL;
+        _deltabasefilename = NULL;
+        _node = NULL;
+        _deltabasenode = NULL;
+        _delta = NULL;
+        _filenamesz = 0;
+        _deltasz = 0;
+      }
+    }
+
+    const char* filename() {
+      return _filename;
+    }
+
+    const char* deltabasefilename() {
+      return _deltabasefilename;
+    }
+
+    const uint8_t* node() {
+      return _node;
+    }
+
+    const uint8_t* deltabasenode() {
+      return _deltabasenode;
+    }
+
+    const uint8_t* delta() {
+      return _delta;
+    }
+
+    uint16_t filenamesz() {
+      return _filenamesz;
+    }
+
+    uint64_t deltasz() {
+      return _deltasz;
+    }
+
+    bool isdone() {
+      return (_filename == NULL);
+    }
+};
+
+/*
+ * This class takes ownership of a delta chain
+ */
+class DeltaChain {
+  private:
+    //C DeltaChain
+    delta_chain_t _chain;
+
+  public:
+    //The constructor does a shallow copy of the delta chain and since the
+    //ownership is taken by this class it is responsible for memory management
+    DeltaChain(delta_chain_t chain) : _chain(chain) {}
+
+    DeltaChain(get_delta_chain_code_t error) {
+      _chain = COMPOUND_LITERAL(delta_chain_t) { GET_DELTA_CHAIN_NOT_FOUND };
+    }
+
+    ~DeltaChain() {
+      freedeltachain(_chain);
+    }
+
+    const DeltaChainLink getlink(const size_t idx) {
+      return DeltaChainLink(&(_chain.delta_chain_links[idx]));
+    }
+
+    size_t linkcount() {
+      return _chain.links_count;
+    }
+
+    get_delta_chain_code_t code() {
+      return _chain.code;
+    }
+
+};
+
+class DeltaChainIterator {
+  private:
+    size_t _index;
+  protected:
+    std::vector< std::shared_ptr<DeltaChain> > _chains;
+    DeltaChainIterator() :
+      _index(0) {}
+    virtual std::shared_ptr<DeltaChain> getNextChain(const Key &key) {
+      return std::make_shared<DeltaChain>(GET_DELTA_CHAIN_NOT_FOUND);
+    }
+  public:
+    DeltaChainIterator(std::shared_ptr<DeltaChain> chain) :
+      _index(0) {
+      _chains.push_back(chain);
+    }
+
+    DeltaChainLink next() {
+      std::shared_ptr<DeltaChain> chain = _chains.back();
+
+      if (_index >= chain->linkcount()) {
+        // If we're not at the end, and we have a callback to fetch more, do the
+        // fetch.
+        bool refreshed = false;
+        if (chain->linkcount() > 0) {
+          DeltaChainLink result = chain->getlink(_index - 1);
+
+          const uint8_t *deltabasenode = result.deltabasenode();
+          if (memcmp(deltabasenode, NULLID, BIN_NODE_SIZE) != 0) {
+            Key key(result.filename(), result.filenamesz(),
+                    (const char*)deltabasenode, BIN_NODE_SIZE);
+
+            std::shared_ptr<DeltaChain> newChain = this->getNextChain(key);
+            if (newChain->code() == GET_DELTA_CHAIN_OK) {
+              // Do not free the old chain, since the iterator consumer may
+              // still be holding references to it.
+              _chains.push_back(newChain);
+              chain = _chains.back();
+              _index = 0;
+              refreshed = true;
+            }
+          }
+        }
+
+        if (!refreshed) {
+          return DeltaChainLink(NULL);
+        }
+      }
+
+      DeltaChainLink result = chain->getlink(_index);
+      _index++;
+
+      return result;
+    }
+};
+
+class DataStore {
+  protected:
+    DataStore() {}
+
+  public:
+    virtual ~DataStore() {}
+
+    virtual DeltaChainIterator getDeltaChain(const Key &key) = 0;
+
+    virtual std::shared_ptr<DeltaChain> getDeltaChainRaw(const Key &key) = 0;
+
+    virtual std::shared_ptr<KeyIterator> getMissing(KeyIterator &missing) = 0;
+
+    virtual bool contains(const Key &key) = 0;
+
+    virtual void markForRefresh() = 0;
+};
+
+#endif // FBHGEXT_DATASTORE_H
diff --git a/cstore/py-datapackstore.h b/cstore/py-datapackstore.h
--- a/cstore/py-datapackstore.h
+++ b/cstore/py-datapackstore.h
@@ -22,6 +22,7 @@
 }
 
 #include "cstore/datapackstore.h"
+#include "cstore/datastore.h"
 #include "cstore/key.h"
 #include "cstore/py-structs.h"
 #include "cstore/pythonutil.h"
@@ -76,15 +77,14 @@
 
     PythonObj resultChain = PyList_New(0);
 
-    delta_chain_link_t *link;
     size_t index = 0;
-    while ((link = chain.next()) != NULL) {
-      PythonObj name = PyString_FromStringAndSize(link->filename, link->filename_sz);
-      PythonObj retnode = PyString_FromStringAndSize((const char *) link->node, NODE_SZ);
+    for (DeltaChainLink link = chain.next(); !link.isdone(); link = chain.next()) {
+      PythonObj name = PyString_FromStringAndSize(link.filename(), link.filenamesz());
+      PythonObj retnode = PyString_FromStringAndSize((const char *) link.node(), NODE_SZ);
       PythonObj deltabasenode = PyString_FromStringAndSize(
-          (const char *) link->deltabase_node, NODE_SZ);
+          (const char *) link.deltabasenode(), NODE_SZ);
       PythonObj delta = PyString_FromStringAndSize(
-          (const char *) link->delta, (Py_ssize_t) link->delta_sz);
+          (const char *) link.delta(), (Py_ssize_t) link.deltasz());
 
       PythonObj tuple = PyTuple_Pack(5, (PyObject*)name, (PyObject*)retnode,
                                         (PyObject*)name, (PyObject*)deltabasenode,
@@ -145,10 +145,10 @@
     PythonObj inputIterator = PyObject_GetIter(keys);
     PythonKeyIterator keysIter(inputIterator);
 
-    DatapackStoreKeyIterator missingIter = self->datapackstore.getMissing(keysIter);
+    std::shared_ptr<KeyIterator> missingIter = self->datapackstore.getMissing(keysIter);
 
     Key *key;
-    while ((key = missingIter.next()) != NULL) {
+    while ((key = missingIter->next()) != NULL) {
       PythonObj missingKey = Py_BuildValue("(s#s#)", key->name.c_str(), key->name.size(),
                                                      key->node, 20);
       if (PyList_Append(result, (PyObject*)missingKey)) {
@@ -232,7 +232,7 @@
   }
 
   try {
-    std::vector<DatapackStore*> stores;
+    std::vector<DataStore*> stores;
     std::vector<PythonObj> pySubStores;
 
     PyObject *item;
@@ -317,14 +317,13 @@
 
     PythonObj resultChain = PyList_New(0);
 
-    delta_chain_link_t *link;
-    while ((link = chain.next()) != NULL) {
-      PythonObj name = PyString_FromStringAndSize(link->filename, link->filename_sz);
-      PythonObj retnode = PyString_FromStringAndSize((const char *) link->node, NODE_SZ);
+    for (DeltaChainLink link = chain.next(); !link.isdone(); link = chain.next()) {
+      PythonObj name = PyString_FromStringAndSize(link.filename(), link.filenamesz());
+      PythonObj retnode = PyString_FromStringAndSize((const char *) link.node(), NODE_SZ);
       PythonObj deltabasenode = PyString_FromStringAndSize(
-          (const char *) link->deltabase_node, NODE_SZ);
+          (const char *) link.deltabasenode(), NODE_SZ);
       PythonObj delta = PyString_FromStringAndSize(
-          (const char *) link->delta, (Py_ssize_t) link->delta_sz);
+          (const char *) link.delta(), (Py_ssize_t) link.deltasz());
 
       PythonObj tuple = PyTuple_Pack(5, (PyObject*)name, (PyObject*)retnode,
                                         (PyObject*)name, (PyObject*)deltabasenode,
diff --git a/cstore/uniondatapackstore.h b/cstore/uniondatapackstore.h
--- a/cstore/uniondatapackstore.h
+++ b/cstore/uniondatapackstore.h
@@ -40,7 +40,7 @@
   private:
     UnionDatapackStore &_store;
   protected:
-    delta_chain_t getNextChain(const Key &key) override;
+    std::shared_ptr<DeltaChain> getNextChain(const Key &key) override;
 
   public:
     UnionDeltaChainIterator(UnionDatapackStore &store, const Key &key) :
@@ -52,9 +52,9 @@
 
 class UnionDatapackStore : public Store {
   public:
-    std::vector<DatapackStore*> _stores;
+    std::vector<DataStore*> _stores;
 
-    UnionDatapackStore(std::vector<DatapackStore*> stores);
+    UnionDatapackStore(std::vector<DataStore*> stores);
 
     ~UnionDatapackStore() override;
 
diff --git a/cstore/uniondatapackstore.cpp b/cstore/uniondatapackstore.cpp
--- a/cstore/uniondatapackstore.cpp
+++ b/cstore/uniondatapackstore.cpp
@@ -16,7 +16,7 @@
 #include "cstore/mpatch.h"
 }
 
-UnionDatapackStore::UnionDatapackStore(std::vector<DatapackStore*> stores) :
+UnionDatapackStore::UnionDatapackStore(std::vector<DataStore*> stores) :
   _stores(stores) {
 }
 
@@ -27,17 +27,17 @@
 }
 
 mpatch_flist* getNextLink(void* container, ssize_t index) {
-  std::vector<delta_chain_link_t*> *links = (std::vector<delta_chain_link_t*>*)container;
+  std::vector<DeltaChainLink> *links = (std::vector<DeltaChainLink>*)container;
 
   if (index < 0 || (size_t)index >= links->size()) {
     return NULL;
   }
 
-  delta_chain_link_t *link = links->at(index);
+  DeltaChainLink link = links->at(index);
 
   struct mpatch_flist *res;
-  if ((mpatch_decode((const char*)link->delta,
-		     (ssize_t)link->delta_sz, &res)) < 0) {
+  if ((mpatch_decode((const char*)link.delta(),
+		     (ssize_t)link.deltasz(), &res)) < 0) {
     throw std::logic_error("invalid patch during patch application");
   }
 
@@ -47,20 +47,19 @@
 ConstantStringRef UnionDatapackStore::get(const Key &key) {
   UnionDeltaChainIterator chain = this->getDeltaChain(key);
 
-  std::vector<delta_chain_link_t*> links;
+  std::vector<DeltaChainLink> links;
 
-  delta_chain_link_t *link;
-  while ((link = chain.next()) != NULL) {
+  for (DeltaChainLink link = chain.next(); !link.isdone(); link = chain.next()) {
     links.push_back(link);
   }
 
-  delta_chain_link_t *fulltextLink = links.back();
+  DeltaChainLink fulltextLink = links.back();
   links.pop_back();
 
   // Short circuit and just return the full text if it's one long
   if (links.size() == 0) {
-    return ConstantStringRef((const char*)fulltextLink->delta,
-                             (size_t)fulltextLink->delta_sz);
+    return ConstantStringRef((const char*)fulltextLink.delta(),
+                             (size_t)fulltextLink.deltasz());
   }
 
   std::reverse(links.begin(), links.end());
@@ -70,15 +69,15 @@
     throw std::logic_error("mpatch failed to fold patches");
   }
 
-  ssize_t outlen = mpatch_calcsize((ssize_t)fulltextLink->delta_sz, patch);
+  ssize_t outlen = mpatch_calcsize((ssize_t)fulltextLink.deltasz(), patch);
   if (outlen < 0) {
     mpatch_lfree(patch);
     throw std::logic_error("mpatch failed to calculate size");
   }
 
   auto result = std::make_shared<std::string>(outlen, '\0');
-  if (mpatch_apply(&(*result)[0], (const char*)fulltextLink->delta,
-		   (ssize_t)fulltextLink->delta_sz, patch) < 0) {
+  if (mpatch_apply(&(*result)[0], (const char*)fulltextLink.delta(),
+		   (ssize_t)fulltextLink.deltasz(), patch) < 0) {
     mpatch_lfree(patch);
     throw std::logic_error("mpatch failed to apply patches");
   }
@@ -87,16 +86,16 @@
   return ConstantStringRef(result);
 }
 
-delta_chain_t UnionDeltaChainIterator::getNextChain(const Key &key) {
-  for(std::vector<DatapackStore*>::iterator it = _store._stores.begin();
+std::shared_ptr<DeltaChain> UnionDeltaChainIterator::getNextChain(const Key &key) {
+  for(std::vector<DataStore*>::iterator it = _store._stores.begin();
       it != _store._stores.end();
       it++) {
-    DatapackStore *substore = *it;
-    delta_chain_t chain = substore->getDeltaChainRaw(key);
-    if (chain.code == GET_DELTA_CHAIN_OK) {
+    DataStore *substore = *it;
+    std::shared_ptr<DeltaChain> chain = substore->getDeltaChainRaw(key);
+
+    if (chain->code() == GET_DELTA_CHAIN_OK) {
       return chain;
     }
-    freedeltachain(chain);
   }
 
   throw MissingKeyError("unable to find delta chain");
@@ -106,8 +105,8 @@
   return UnionDeltaChainIterator(*this, key);
 }
 
-Key *UnionDatapackStoreKeyIterator::next() {
-  Key *key;
+Key* UnionDatapackStoreKeyIterator::next() {
+  Key* key;
   while ((key = _missing.next()) != NULL) {
     if (!_store.contains(*key)) {
       return key;
@@ -118,10 +117,10 @@
 }
 
 bool UnionDatapackStore::contains(const Key &key) {
-  for(std::vector<DatapackStore*>::iterator it = _stores.begin();
+  for(std::vector<DataStore*>::iterator it = _stores.begin();
       it != _stores.end();
       it++) {
-    DatapackStore *substore = *it;
+    DataStore *substore = *it;
     if (substore->contains(key)) {
       return true;
     }
@@ -134,10 +133,10 @@
 }
 
 void UnionDatapackStore::markForRefresh() {
-  for(std::vector<DatapackStore*>::iterator it = _stores.begin();
+  for(std::vector<DataStore*>::iterator it = _stores.begin();
       it != _stores.end();
       it++) {
-    DatapackStore *substore = *it;
+    DataStore *substore = *it;
     substore->markForRefresh();
   }
 }
diff --git a/tests/test-check-code-hg.t b/tests/test-check-code-hg.t
--- a/tests/test-check-code-hg.t
+++ b/tests/test-check-code-hg.t
@@ -64,6 +64,7 @@
   Skipping clib/sha1.h it has no-che?k-code (glob)
   Skipping cstore/datapackstore.cpp it has no-che?k-code (glob)
   Skipping cstore/datapackstore.h it has no-che?k-code (glob)
+  Skipping cstore/datastore.h it has no-che?k-code (glob)
   Skipping cstore/key.h it has no-che?k-code (glob)
   Skipping cstore/match.h it has no-che?k-code (glob)
   Skipping cstore/py-cdatapack.h it has no-che?k-code (glob)