common/SloppyCRCMap: add type to sloppily track crcs

Signed-off-by: Sage Weil <sage@inktank.com>

sloppy

6 files changed, 381 insertions, 0 deletions

diff --git a/src/common/Makefile.am b/src/common/Makefile.am
index 3526118205f..deddc5d831c 100644
--- a/src/common/Makefile.am
+++ b/src/common/Makefile.am
@@ -4,6 +4,7 @@ libcommon_la_SOURCES = \
 	common/LogClient.cc \
 	common/LogEntry.cc \
 	common/PrebufferedStreambuf.cc \
+	common/SloppyCRCMap.cc \
 	common/BackTrace.cc \
 	common/perf_counters.cc \
 	common/Mutex.cc \
@@ -120,6 +121,7 @@ noinst_HEADERS += \
 	common/LogClient.h \
 	common/LogEntry.h \
 	common/Preforker.h \
+	common/SloppyCRCMap.h \
 	common/WorkQueue.h \
 	common/PrioritizedQueue.h \
 	common/ceph_argparse.h \
diff --git a/src/common/SloppyCRCMap.cc b/src/common/SloppyCRCMap.cc
new file mode 100644
index 00000000000..7924ae6e8a7
--- /dev/null
+++ b/src/common/SloppyCRCMap.cc
@@ -0,0 +1,180 @@
+// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- 
+// vim: ts=8 sw=2 smarttab
+
+#include "common/SloppyCRCMap.h"
+#include "common/Formatter.h"
+
+void SloppyCRCMap::write(uint64_t offset, uint64_t len, const bufferlist& bl,
+			 std::ostream *out)
+{
+  int64_t left = len;
+  uint64_t pos = offset;
+  unsigned o = offset % block_size;
+  if (o) {
+    crc_map.erase(offset - o);
+    if (out)
+      *out << "write invalidate " << (offset - o) << "\n";
+    pos += (block_size - o);
+    left -= (block_size - o);
+  }
+  while (left >= block_size) {
+    bufferlist t;
+    t.substr_of(bl, pos - offset, block_size);
+    crc_map[pos] = t.crc32c(crc_iv);
+    if (out)
+      *out << "write set " << pos << " " << crc_map[pos] << "\n";
+    pos += block_size;
+    left -= block_size;
+  }
+  if (left > 0) {
+    crc_map.erase(pos);
+    if (out)
+      *out << "write invalidate " << pos << "\n";
+  }
+}
+
+int SloppyCRCMap::read(uint64_t offset, uint64_t len, const bufferlist& bl,
+		       std::ostream *err)
+{
+  int errors = 0;
+  int64_t left = len;
+  uint64_t pos = offset;
+  unsigned o = offset % block_size;
+  if (o) {
+    pos += (block_size - o);
+    left -= (block_size - o);
+  }
+  while (left >= block_size) {
+    // FIXME: this could be more efficient if we avoid doing a find()
+    // on each iteration
+    std::map<uint64_t,uint32_t>::iterator p = crc_map.find(pos);
+    if (p != crc_map.end()) {
+      bufferlist t;
+      t.substr_of(bl, pos - offset, block_size);
+      uint32_t crc = t.crc32c(crc_iv);
+      if (p->second != crc) {
+	errors++;
+	if (err)
+	  *err << "offset " << pos << " len " << block_size
+	       << " has crc " << crc << " expected " << p->second << "\n";
+      }
+    }
+    pos += block_size;
+    left -= block_size;
+  }
+  return errors;  
+}
+
+void SloppyCRCMap::truncate(uint64_t offset)
+{
+  offset -= offset % block_size;
+  std::map<uint64_t,uint32_t>::iterator p = crc_map.lower_bound(offset);
+  while (p != crc_map.end())
+    crc_map.erase(p++);
+}
+
+void SloppyCRCMap::zero(uint64_t offset, uint64_t len)
+{
+  int64_t left = len;
+  uint64_t pos = offset;
+  unsigned o = offset % block_size;
+  if (o) {
+    crc_map.erase(offset - o);
+    pos += (block_size - o);
+    left -= (block_size - o);
+  }
+  while (left >= block_size) {
+    crc_map[pos] = zero_crc;
+    pos += block_size;
+    left -= block_size;
+  }
+  if (left > 0)
+    crc_map.erase(pos);
+}
+
+void SloppyCRCMap::clone_range(uint64_t offset, uint64_t len,
+			       uint64_t srcoff, const SloppyCRCMap& src,
+			       std::ostream *out)
+{
+  int64_t left = len;
+  uint64_t pos = offset;
+  uint64_t srcpos = srcoff;
+  unsigned o = offset % block_size;
+  if (o) {
+    crc_map.erase(offset - o);
+    pos += (block_size - o);
+    srcpos += (block_size - o);
+    left -= (block_size - o);
+    if (out)
+      *out << "clone_range invalidate " << (offset - o) << "\n";
+  }
+  while (left >= block_size) {
+    // FIXME: this could be more efficient.
+    if (block_size == src.block_size) {
+      map<uint64_t,uint32_t>::const_iterator p = src.crc_map.find(srcpos);
+      if (p != src.crc_map.end()) {
+	crc_map[pos] = p->second;
+	if (out)
+	  *out << "clone_range copy " << pos << " " << p->second << "\n";
+      } else {
+	crc_map.erase(pos);
+	if (out)
+	  *out << "clone_range invalidate " << pos << "\n";
+      }
+    } else {
+      crc_map.erase(pos);
+      if (out)
+	*out << "clone_range invalidate " << pos << "\n";
+    }
+    pos += block_size;
+    srcpos += block_size;
+    left -= block_size;
+  }
+  if (left > 0) {
+    crc_map.erase(pos);
+    if (out)
+      *out << "clone_range invalidate " << pos << "\n";
+  }
+}
+
+void SloppyCRCMap::encode(bufferlist& bl) const
+{
+  ENCODE_START(1, 1, bl);
+  ::encode(block_size, bl);
+  ::encode(crc_map, bl);
+  ENCODE_FINISH(bl);
+}
+
+void SloppyCRCMap::decode(bufferlist::iterator& bl)
+{
+  DECODE_START(1, bl);
+  uint32_t bs;
+  ::decode(bs, bl);
+  set_block_size(bs);
+  ::decode(crc_map, bl);
+  DECODE_FINISH(bl);
+}
+
+void SloppyCRCMap::dump(Formatter *f) const
+{
+  f->dump_unsigned("block_size", block_size);
+  f->open_array_section("crc_map");
+  for (map<uint64_t,uint32_t>::const_iterator p = crc_map.begin(); p != crc_map.end(); ++p) {
+    f->open_object_section("crc");
+    f->dump_unsigned("offset", p->first);
+    f->dump_unsigned("crc", p->second);
+    f->close_section();
+  }
+  f->close_section();
+}
+
+void SloppyCRCMap::generate_test_instances(list<SloppyCRCMap*>& ls)
+{
+  ls.push_back(new SloppyCRCMap);
+  ls.push_back(new SloppyCRCMap(2));
+  bufferlist bl;
+  bl.append("some data");
+  ls.back()->write(1, bl.length(), bl);
+  ls.back()->write(10, bl.length(), bl);
+  ls.back()->zero(4, 2);
+}
diff --git a/src/common/SloppyCRCMap.h b/src/common/SloppyCRCMap.h
new file mode 100644
index 00000000000..c07b4d9bb9d
--- /dev/null
+++ b/src/common/SloppyCRCMap.h
@@ -0,0 +1,78 @@
+// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- 
+// vim: ts=8 sw=2 smarttab
+
+#ifndef CEPH_COMMON_SLOPPYCRCMAP_H
+#define CEPH_COMMON_SLOPPYCRCMAP_H
+
+#include "include/types.h"
+#include "include/encoding.h"
+
+#include <map>
+#include <ostream>
+
+/**
+ * SloppyCRCMap
+ *
+ * Opportunistically track CRCs on any reads or writes that cover full
+ * blocks.  Verify read results when we have CRC data available for
+ * the given extent.
+ */
+class SloppyCRCMap {
+  static const int crc_iv = 0xffffffff;
+
+  std::map<uint64_t, uint32_t> crc_map;  // offset -> crc(-1)
+  uint32_t block_size;
+  uint32_t zero_crc;
+
+public:
+  SloppyCRCMap(uint32_t b=0) {
+    set_block_size(b);
+  }
+
+  void set_block_size(uint32_t b) {
+    block_size = b;
+    //zero_crc = ceph_crc32c(0xffffffff, NULL, block_size);
+    if (b) {
+      bufferlist bl;
+      bufferptr bp(block_size);
+      bp.zero();
+      bl.append(bp);
+      zero_crc = bl.crc32c(crc_iv);
+    } else {
+      zero_crc = crc_iv;
+    }
+  }
+
+  /// update based on a write
+  void write(uint64_t offset, uint64_t len, const bufferlist& bl,
+	     std::ostream *out = NULL);
+
+  /// update based on a truncate
+  void truncate(uint64_t offset);
+
+  /// update based on a zero/punch_hole
+  void zero(uint64_t offset, uint64_t len);
+
+  /// update based on a zero/punch_hole
+  void clone_range(uint64_t offset, uint64_t len, uint64_t srcoff, const SloppyCRCMap& src,
+		   std::ostream *out = NULL);
+
+  /**
+   * validate a read result
+   *
+   * @param offset offset
+   * @param length length
+   * @param bl data read
+   * @param err option ostream to describe errors in detail
+   * @returns error count, 0 for success
+   */
+  int read(uint64_t offset, uint64_t len, const bufferlist& bl, std::ostream *err);
+
+  void encode(bufferlist& bl) const;
+  void decode(bufferlist::iterator& bl);
+  void dump(Formatter *f) const;
+  static void generate_test_instances(list<SloppyCRCMap*>& ls);
+};
+WRITE_CLASS_ENCODER(SloppyCRCMap)
+
+#endif
diff --git a/src/test/Makefile.am b/src/test/Makefile.am
index 32fee301e4c..debe18ff907 100644
--- a/src/test/Makefile.am
+++ b/src/test/Makefile.am
@@ -263,6 +263,11 @@ unittest_sharedptr_registry_CXXFLAGS = $(UNITTEST_CXXFLAGS)
 unittest_sharedptr_registry_LDADD = $(UNITTEST_LDADD) $(CEPH_GLOBAL)
 check_PROGRAMS += unittest_sharedptr_registry
 
+unittest_sloppy_crc_map_SOURCES = test/common/test_sloppy_crc_map.cc
+unittest_sloppy_crc_map_CXXFLAGS = $(UNITTEST_CXXFLAGS)
+unittest_sloppy_crc_map_LDADD = $(UNITTEST_LDADD) $(CEPH_GLOBAL)
+check_PROGRAMS += unittest_sloppy_crc_map
+
 unittest_util_SOURCES = test/common/test_util.cc
 unittest_util_CXXFLAGS = $(UNITTEST_CXXFLAGS)
 unittest_util_LDADD = $(LIBCOMMON) -lm $(UNITTEST_LDADD) $(CRYPTO_LIBS) $(EXTRALIBS)
diff --git a/src/test/common/test_sloppy_crc_map.cc b/src/test/common/test_sloppy_crc_map.cc
new file mode 100644
index 00000000000..2650f4f960d
--- /dev/null
+++ b/src/test/common/test_sloppy_crc_map.cc
@@ -0,0 +1,113 @@
+// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
+// vim: ts=8 sw=2 smarttab
+
+#include "common/SloppyCRCMap.h"
+#include "common/Formatter.h"
+#include <gtest/gtest.h>
+
+void dump(const SloppyCRCMap& scm)
+{
+  Formatter *f = new_formatter("json-pretty");
+  f->open_object_section("map");
+  scm.dump(f);
+  f->close_section();
+  f->flush(cout);
+  delete f;
+}
+
+TEST(SloppyCRCMap, basic) {
+  SloppyCRCMap scm(4);
+
+  bufferlist a, b;
+  a.append("The quick brown fox jumped over a fence whose color I forget.");
+  b.append("asdf");
+
+  scm.write(0, a.length(), a);
+  if (0)
+    dump(scm);
+  ASSERT_EQ(0, scm.read(0, a.length(), a, &cout));
+
+  scm.write(12, b.length(), b);
+  if (0)
+    dump(scm);
+
+  ASSERT_EQ(0, scm.read(12, b.length(), b, &cout));
+  ASSERT_EQ(1, scm.read(0, a.length(), a, &cout));
+}
+
+TEST(SloppyCRCMap, truncate) {
+  SloppyCRCMap scm(4);
+
+  bufferlist a, b;
+  a.append("asdf");
+  b.append("qwer");
+
+  scm.write(0, a.length(), a);
+  scm.write(4, a.length(), a);
+  ASSERT_EQ(0, scm.read(4, 4, a, &cout));
+  ASSERT_EQ(1, scm.read(4, 4, b, &cout));
+  scm.truncate(4);
+  ASSERT_EQ(0, scm.read(4, 4, b, &cout));
+}
+
+TEST(SloppyCRCMap, zero) {
+  SloppyCRCMap scm(4);
+
+  bufferlist a, b;
+  a.append("asdf");
+  b.append("qwer");
+
+  scm.write(0, a.length(), a);
+  scm.write(4, a.length(), a);
+  ASSERT_EQ(0, scm.read(4, 4, a, &cout));
+  ASSERT_EQ(1, scm.read(4, 4, b, &cout));
+  scm.zero(4, 4);
+  ASSERT_EQ(1, scm.read(4, 4, a, &cout));
+  ASSERT_EQ(1, scm.read(4, 4, b, &cout));
+
+  bufferptr bp(4);
+  bp.zero();
+  bufferlist c;
+  c.append(bp);
+  ASSERT_EQ(0, scm.read(0, 4, a, &cout));
+  ASSERT_EQ(0, scm.read(4, 4, c, &cout));
+  scm.zero(0, 15);
+  ASSERT_EQ(1, scm.read(0, 4, a, &cout));
+  ASSERT_EQ(0, scm.read(0, 4, c, &cout));
+}
+
+TEST(SloppyCRCMap, clone_range) {
+  SloppyCRCMap src(4);
+  SloppyCRCMap dst(4);
+
+  bufferlist a, b;
+  a.append("asdfghjkl");
+  b.append("qwertyui");
+
+  src.write(0, a.length(), a);
+  src.write(8, a.length(), a);
+  src.write(16, a.length(), a);
+
+  dst.write(0, b.length(), b);
+  dst.clone_range(0, 8, 0, src);
+  ASSERT_EQ(2, dst.read(0, 8, b, &cout));
+  ASSERT_EQ(0, dst.read(8, 8, b, &cout));
+
+  dst.write(16, b.length(), b);
+  ASSERT_EQ(2, dst.read(16, 8, a, &cout));
+  dst.clone_range(16, 8, 16, src);
+  ASSERT_EQ(0, dst.read(16, 8, a, &cout));
+
+  dst.write(16, b.length(), b);
+  ASSERT_EQ(1, dst.read(16, 4, a, &cout));
+  dst.clone_range(16, 8, 2, src);
+  ASSERT_EQ(0, dst.read(16, 4, a, &cout));
+
+  dst.write(0, b.length(), b);
+  dst.write(8, b.length(), b);
+  ASSERT_EQ(2, dst.read(0, 8, a, &cout));
+  ASSERT_EQ(2, dst.read(8, 8, a, &cout));
+  dst.clone_range(2, 8, 0, src);
+  ASSERT_EQ(0, dst.read(0, 8, a, &cout));
+  ASSERT_EQ(0, dst.read(8, 4, a, &cout));
+}
diff --git a/src/test/encoding/types.h b/src/test/encoding/types.h
index 7f2b4d9db5d..6dd180bc198 100644
--- a/src/test/encoding/types.h
+++ b/src/test/encoding/types.h
@@ -16,6 +16,9 @@ TYPE(LogEntryKey)
 TYPE(LogEntry)
 TYPE(LogSummary)
 
+#include "common/SloppyCRCMap.h"
+TYPE(SloppyCRCMap)
+
 #include "msg/msg_types.h"
 TYPE(entity_name_t)
 TYPE(entity_addr_t)