[ceph.git] / ceph / src / test / librbd / cache / pwl / test_WriteLogMap.cc

// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
// vim: ts=8 sw=2 smarttab

#include "test/librbd/test_fixture.h"
#include "test/librbd/test_support.h"

#include "librbd/cache/pwl/LogMap.cc"

void register_test_write_log_map() {
}

namespace librbd {
namespace cache {
namespace pwl {

using namespace std;

struct TestLogEntry {
  uint64_t image_offset_bytes;
  uint64_t write_bytes;
  uint32_t referring_map_entries = 0;
  TestLogEntry(const uint64_t image_offset_bytes, const uint64_t write_bytes)
    : image_offset_bytes(image_offset_bytes), write_bytes(write_bytes) {
  }
  uint64_t get_offset_bytes() {
    return image_offset_bytes;
  }
  uint64_t get_write_bytes() {
    return write_bytes;
  }
  BlockExtent block_extent() {
    return BlockExtent(image_offset_bytes, image_offset_bytes + write_bytes);
  }
  uint32_t get_map_ref() {
    return referring_map_entries;
  }
  void inc_map_ref() {
    referring_map_entries++;
  }
  void dec_map_ref() {
    referring_map_entries--;
  }
  friend std::ostream &operator<<(std::ostream &os,
                                  const TestLogEntry &entry) {
    os << "referring_map_entries=" << entry.referring_map_entries << ", "
       << "image_offset_bytes=" << entry.image_offset_bytes << ", "
       << "write_bytes=" << entry.write_bytes;
    return os;
  };
};

typedef std::list<std::shared_ptr<TestLogEntry>> TestLogEntries;
typedef LogMapEntry<TestLogEntry> TestMapEntry;
typedef LogMapEntries<TestLogEntry> TestLogMapEntries;
typedef LogMap<TestLogEntry> TestLogMap;

class TestWriteLogMap : public TestFixture {
public:
  void SetUp() override {
    TestFixture::SetUp();
    m_cct = reinterpret_cast<CephContext*>(m_ioctx.cct());
  }

  CephContext *m_cct;
};

TEST_F(TestWriteLogMap, Simple) {
  TestLogEntries es;
  TestLogMapEntries lme;
  TestLogMap  map(m_cct);

  /* LogEntry takes offset, length, in bytes */
  auto e1 = make_shared<TestLogEntry>(4, 8);
  TestLogEntry *e1_ptr = e1.get();
  ASSERT_EQ(4, e1_ptr->get_offset_bytes());
  ASSERT_EQ(8, e1_ptr->get_write_bytes());
  map.add_log_entry(e1);

  /* BlockExtent takes first, last, in blocks */
  TestLogMapEntries found0 = map.find_map_entries(BlockExtent(0, 100));
  int numfound = found0.size();
  /* Written range includes the single write above */
  ASSERT_EQ(1, numfound);
  ASSERT_EQ(e1, found0.front().log_entry);

  /* Nothing before that */
  found0 = map.find_map_entries(BlockExtent(0, 3));
  numfound = found0.size();
  ASSERT_EQ(0, numfound);

  /* Nothing after that */
  found0 = map.find_map_entries(BlockExtent(12, 99));
  numfound = found0.size();
  ASSERT_EQ(0, numfound);

  /* 4-11 will be e1 */
  for (int i=4; i<12; i++) {
    TestLogMapEntries found0 = map.find_map_entries(BlockExtent(i, i + 1));
    int numfound = found0.size();
    ASSERT_EQ(1, numfound);
    ASSERT_EQ(e1, found0.front().log_entry);
  }

  map.remove_log_entry(e1);
  /* Nothing should be found */
  for (int i=4; i<12; i++) {
    TestLogMapEntries found0 = map.find_map_entries(BlockExtent(i, i + 1));
    int numfound = found0.size();
    ASSERT_EQ(0, numfound);
  }
}

TEST_F(TestWriteLogMap, OverlapFront) {
  TestLogMap map(m_cct);

  auto e0 = make_shared<TestLogEntry>(4, 8);
  map.add_log_entry(e0);
  /* replaces block 4-7 of e0 */
  auto e1 = make_shared<TestLogEntry>(0, 8);
  map.add_log_entry(e1);

  /* Written range includes the two writes above */
  TestLogMapEntries found0 = map.find_map_entries(BlockExtent(0, 100));
  int numfound = found0.size();
  ASSERT_EQ(2, numfound);
  ASSERT_EQ(e1, found0.front().log_entry);
  ASSERT_EQ(0, found0.front().block_extent.block_start);
  ASSERT_EQ(8, found0.front().block_extent.block_end);
  found0.pop_front();
  ASSERT_EQ(e0, found0.front().log_entry);
  ASSERT_EQ(8, found0.front().block_extent.block_start);
  ASSERT_EQ(12, found0.front().block_extent.block_end);

  /* 0-7 will be e1 */
  for (int i=0; i<8; i++) {
    TestLogMapEntries found0 = map.find_map_entries(BlockExtent(i, i + 1));
    int numfound = found0.size();
    ASSERT_EQ(1, numfound);
    ASSERT_EQ(e1, found0.front().log_entry);
  }

  /* 8-11 will be e0 */
  for (int i=8; i<12; i++) {
    TestLogMapEntries found0 = map.find_map_entries(BlockExtent(i, i + 1));
    int numfound = found0.size();
    ASSERT_EQ(1, numfound);
    ASSERT_EQ(e0, found0.front().log_entry);
  }
}

TEST_F(TestWriteLogMap, OverlapBack) {
  TestLogMap map(m_cct);

  auto e0 = make_shared<TestLogEntry>(0, 8);
  map.add_log_entry(e0);
  /* replaces block 4-7 of e0 */
  auto e1 = make_shared<TestLogEntry>(4, 8);
  map.add_log_entry(e1);

  /* Written range includes the two writes above */
  TestLogMapEntries found0 = map.find_map_entries(BlockExtent(0, 100));
  int numfound = found0.size();
  ASSERT_EQ(2, numfound);
  ASSERT_EQ(e0, found0.front().log_entry);
  ASSERT_EQ(0, found0.front().block_extent.block_start);
  ASSERT_EQ(4, found0.front().block_extent.block_end);
  found0.pop_front();
  ASSERT_EQ(e1, found0.front().log_entry);
  ASSERT_EQ(4, found0.front().block_extent.block_start);
  ASSERT_EQ(12, found0.front().block_extent.block_end);

  /* 0-3 will be e0 */
  for (int i=0; i<4; i++) {
    TestLogMapEntries found0 = map.find_map_entries(BlockExtent(i, i + 1));
    int numfound = found0.size();
    ASSERT_EQ(1, numfound);
    ASSERT_EQ(e0, found0.front().log_entry);
  }

  /* 4-11 will be e1 */
  for (int i=4; i<12; i++) {
    TestLogMapEntries found0 = map.find_map_entries(BlockExtent(i, i + 1));
    int numfound = found0.size();
    ASSERT_EQ(1, numfound);
    ASSERT_EQ(e1, found0.front().log_entry);
  }

  map.remove_log_entry(e0);

  /* 0-3 will find nothing */
  for (int i=0; i<4; i++) {
    TestLogMapEntries found0 = map.find_map_entries(BlockExtent(i, i + 1));
    int numfound = found0.size();
    ASSERT_EQ(0, numfound);
  }

  /* 4-11 will still be e1 */
  for (int i=4; i<12; i++) {
    TestLogMapEntries found0 = map.find_map_entries(BlockExtent(i, i + 1));
    int numfound = found0.size();
    ASSERT_EQ(1, numfound);
    ASSERT_EQ(e1, found0.front().log_entry);
  }

}

TEST_F(TestWriteLogMap, OverlapMiddle) {
  TestLogMap map(m_cct);

  auto e0 = make_shared<TestLogEntry>(0, 1);
  map.add_log_entry(e0);

  TestLogMapEntries found0 = map.find_map_entries(BlockExtent(0, 1));
  int numfound = found0.size();
  ASSERT_EQ(1, numfound);
  ASSERT_EQ(e0, found0.front().log_entry);
  TestLogEntries entries = map.find_log_entries(BlockExtent(0, 1));
  int entriesfound = entries.size();
  ASSERT_EQ(1, entriesfound);
  ASSERT_EQ(e0, entries.front());

  auto e1 = make_shared<TestLogEntry>(1, 1);
  map.add_log_entry(e1);

  found0 = map.find_map_entries(BlockExtent(1, 2));
  numfound = found0.size();
  ASSERT_EQ(1, numfound);
  ASSERT_EQ(e1, found0.front().log_entry);
  entries = map.find_log_entries(BlockExtent(1, 2));
  entriesfound = entries.size();
  ASSERT_EQ(1, entriesfound);
  ASSERT_EQ(e1, entries.front());

  auto e2 = make_shared<TestLogEntry>(2, 1);
  map.add_log_entry(e2);

  found0 = map.find_map_entries(BlockExtent(2, 3));
  numfound = found0.size();
  ASSERT_EQ(1, numfound);
  ASSERT_EQ(e2, found0.front().log_entry);
  entries = map.find_log_entries(BlockExtent(2, 3));
  entriesfound = entries.size();
  ASSERT_EQ(1, entriesfound);
  ASSERT_EQ(e2, entries.front());

  /* replaces e1 */
  auto e3 = make_shared<TestLogEntry>(1, 1);
  map.add_log_entry(e3);

  found0 = map.find_map_entries(BlockExtent(1, 2));
  numfound = found0.size();
  ASSERT_EQ(1, numfound);
  ASSERT_EQ(e3, found0.front().log_entry);
  entries = map.find_log_entries(BlockExtent(1, 2));
  entriesfound = entries.size();
  ASSERT_EQ(1, entriesfound);
  ASSERT_EQ(e3, entries.front());

  found0 = map.find_map_entries(BlockExtent(0, 100));
  numfound = found0.size();
  ASSERT_EQ(3, numfound);
  ASSERT_EQ(e0, found0.front().log_entry);
  found0.pop_front();
  ASSERT_EQ(e3, found0.front().log_entry);
  found0.pop_front();
  ASSERT_EQ(e2, found0.front().log_entry);
  entries = map.find_log_entries(BlockExtent(0, 100));
  entriesfound = entries.size();
  ASSERT_EQ(3, entriesfound);
  ASSERT_EQ(e0, entries.front());
  entries.pop_front();
  ASSERT_EQ(e3, entries.front());
  entries.pop_front();
  ASSERT_EQ(e2, entries.front());

  entries.clear();
  entries.emplace_back(e0);
  entries.emplace_back(e1);
  map.remove_log_entries(entries);

  found0 = map.find_map_entries(BlockExtent(0, 100));
  numfound = found0.size();
  ASSERT_EQ(2, numfound);
  ASSERT_EQ(e3, found0.front().log_entry);
  found0.pop_front();
  ASSERT_EQ(e2, found0.front().log_entry);
}

TEST_F(TestWriteLogMap, OverlapSplit) {
  TestLogMap map(m_cct);

  auto e0 = make_shared<TestLogEntry>(0, 8);
  map.add_log_entry(e0);

  /* Splits e0 at 1 */
  auto e1 = make_shared<TestLogEntry>(1, 1);
  map.add_log_entry(e1);

  /* Splits e0 again at 4 */
  auto e2 = make_shared<TestLogEntry>(4, 2);
  map.add_log_entry(e2);

  /* Replaces one block of e2, and one of e0 */
  auto e3 = make_shared<TestLogEntry>(5, 2);
  map.add_log_entry(e3);

  /* Expecting: 0:e0, 1:e1, 2..3:e0, 4:e2, 5..6:e3, 7:e0 */
  TestLogMapEntries found0 = map.find_map_entries(BlockExtent(0, 100));
  int numfound = found0.size();
  ASSERT_EQ(6, numfound);
  ASSERT_EQ(e0, found0.front().log_entry);
  ASSERT_EQ(0, found0.front().block_extent.block_start);
  ASSERT_EQ(1, found0.front().block_extent.block_end);
  found0.pop_front();
  ASSERT_EQ(e1, found0.front().log_entry);
  ASSERT_EQ(1, found0.front().block_extent.block_start);
  ASSERT_EQ(2, found0.front().block_extent.block_end);
  found0.pop_front();
  ASSERT_EQ(e0, found0.front().log_entry);
  ASSERT_EQ(2, found0.front().block_extent.block_start);
  ASSERT_EQ(4, found0.front().block_extent.block_end);
  found0.pop_front();
  ASSERT_EQ(e2, found0.front().log_entry);
  ASSERT_EQ(4, found0.front().block_extent.block_start);
  ASSERT_EQ(5, found0.front().block_extent.block_end);
  found0.pop_front();
  ASSERT_EQ(e3, found0.front().log_entry);
  ASSERT_EQ(5, found0.front().block_extent.block_start);
  ASSERT_EQ(7, found0.front().block_extent.block_end);
  found0.pop_front();
  ASSERT_EQ(e0, found0.front().log_entry);
  ASSERT_EQ(7, found0.front().block_extent.block_start);
  ASSERT_EQ(8, found0.front().block_extent.block_end);
}

} // namespace pwl
} // namespace cache
} // namespace librbd
Commit	Line	Data
f67539c2 TL	1	// -- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t --
	2	// vim: ts=8 sw=2 smarttab
	3
	4	#include "test/librbd/test_fixture.h"
	5	#include "test/librbd/test_support.h"
	6
	7	#include "librbd/cache/pwl/LogMap.cc"
	8
	9	void register_test_write_log_map() {
	10	}
	11
	12	namespace librbd {
	13	namespace cache {
	14	namespace pwl {
	15
20effc67 TL	16	using namespace std;
20effc67 TL	17
f67539c2 TL	18	struct TestLogEntry {
	19	uint64_t image_offset_bytes;
	20	uint64_t write_bytes;
	21	uint32_t referring_map_entries = 0;
	22	TestLogEntry(const uint64_t image_offset_bytes, const uint64_t write_bytes)
	23	: image_offset_bytes(image_offset_bytes), write_bytes(write_bytes) {
	24	}
	25	uint64_t get_offset_bytes() {
	26	return image_offset_bytes;
	27	}
	28	uint64_t get_write_bytes() {
	29	return write_bytes;
	30	}
	31	BlockExtent block_extent() {
	32	return BlockExtent(image_offset_bytes, image_offset_bytes + write_bytes);
	33	}
	34	uint32_t get_map_ref() {
	35	return referring_map_entries;
	36	}
	37	void inc_map_ref() {
	38	referring_map_entries++;
	39	}
	40	void dec_map_ref() {
	41	referring_map_entries--;
	42	}
	43	friend std::ostream &operator<<(std::ostream &os,
	44	const TestLogEntry &entry) {
	45	os << "referring_map_entries=" << entry.referring_map_entries << ", "
	46	<< "image_offset_bytes=" << entry.image_offset_bytes << ", "
	47	<< "write_bytes=" << entry.write_bytes;
	48	return os;
	49	};
	50	};
	51
	52	typedef std::list<std::shared_ptr<TestLogEntry>> TestLogEntries;
	53	typedef LogMapEntry<TestLogEntry> TestMapEntry;
	54	typedef LogMapEntries<TestLogEntry> TestLogMapEntries;
	55	typedef LogMap<TestLogEntry> TestLogMap;
	56
	57	class TestWriteLogMap : public TestFixture {
	58	public:
	59	void SetUp() override {
	60	TestFixture::SetUp();
	61	m_cct = reinterpret_cast<CephContext*>(m_ioctx.cct());
	62	}
	63
	64	CephContext *m_cct;
	65	};
	66
	67	TEST_F(TestWriteLogMap, Simple) {
	68	TestLogEntries es;
	69	TestLogMapEntries lme;
	70	TestLogMap map(m_cct);
	71
	72	/* LogEntry takes offset, length, in bytes */
	73	auto e1 = make_shared<TestLogEntry>(4, 8);
	74	TestLogEntry *e1_ptr = e1.get();
	75	ASSERT_EQ(4, e1_ptr->get_offset_bytes());
	76	ASSERT_EQ(8, e1_ptr->get_write_bytes());
	77	map.add_log_entry(e1);
	78
	79	/* BlockExtent takes first, last, in blocks */
	80	TestLogMapEntries found0 = map.find_map_entries(BlockExtent(0, 100));
	81	int numfound = found0.size();
82	/* Written range includes the single write above */
83	ASSERT_EQ(1, numfound);
84	ASSERT_EQ(e1, found0.front().log_entry);
85
86	/* Nothing before that */
87	found0 = map.find_map_entries(BlockExtent(0, 3));
88	numfound = found0.size();
89	ASSERT_EQ(0, numfound);
90
91	/* Nothing after that */
92	found0 = map.find_map_entries(BlockExtent(12, 99));
93	numfound = found0.size();
94	ASSERT_EQ(0, numfound);
95
96	/* 4-11 will be e1 */
97	for (int i=4; i<12; i++) {
98	TestLogMapEntries found0 = map.find_map_entries(BlockExtent(i, i + 1));
99	int numfound = found0.size();
100	ASSERT_EQ(1, numfound);
101	ASSERT_EQ(e1, found0.front().log_entry);
102	}
103
104	map.remove_log_entry(e1);
105	/* Nothing should be found */
106	for (int i=4; i<12; i++) {
107	TestLogMapEntries found0 = map.find_map_entries(BlockExtent(i, i + 1));
108	int numfound = found0.size();
109	ASSERT_EQ(0, numfound);
110	}
111	}
112
113	TEST_F(TestWriteLogMap, OverlapFront) {
114	TestLogMap map(m_cct);
115
116	auto e0 = make_shared<TestLogEntry>(4, 8);
117	map.add_log_entry(e0);
118	/* replaces block 4-7 of e0 */
119	auto e1 = make_shared<TestLogEntry>(0, 8);
120	map.add_log_entry(e1);
121
122	/* Written range includes the two writes above */
123	TestLogMapEntries found0 = map.find_map_entries(BlockExtent(0, 100));
124	int numfound = found0.size();
125	ASSERT_EQ(2, numfound);
126	ASSERT_EQ(e1, found0.front().log_entry);
127	ASSERT_EQ(0, found0.front().block_extent.block_start);
128	ASSERT_EQ(8, found0.front().block_extent.block_end);
129	found0.pop_front();
130	ASSERT_EQ(e0, found0.front().log_entry);
131	ASSERT_EQ(8, found0.front().block_extent.block_start);
132	ASSERT_EQ(12, found0.front().block_extent.block_end);
133
134	/* 0-7 will be e1 */
135	for (int i=0; i<8; i++) {
136	TestLogMapEntries found0 = map.find_map_entries(BlockExtent(i, i + 1));
137	int numfound = found0.size();
138	ASSERT_EQ(1, numfound);
139	ASSERT_EQ(e1, found0.front().log_entry);
140	}
141
142	/* 8-11 will be e0 */
143	for (int i=8; i<12; i++) {
144	TestLogMapEntries found0 = map.find_map_entries(BlockExtent(i, i + 1));
145	int numfound = found0.size();
146	ASSERT_EQ(1, numfound);
147	ASSERT_EQ(e0, found0.front().log_entry);
148	}
149	}
150
151	TEST_F(TestWriteLogMap, OverlapBack) {
152	TestLogMap map(m_cct);
153
154	auto e0 = make_shared<TestLogEntry>(0, 8);
155	map.add_log_entry(e0);
156	/* replaces block 4-7 of e0 */
157	auto e1 = make_shared<TestLogEntry>(4, 8);
158	map.add_log_entry(e1);
159
160	/* Written range includes the two writes above */
161	TestLogMapEntries found0 = map.find_map_entries(BlockExtent(0, 100));
162	int numfound = found0.size();
163	ASSERT_EQ(2, numfound);
164	ASSERT_EQ(e0, found0.front().log_entry);
165	ASSERT_EQ(0, found0.front().block_extent.block_start);
166	ASSERT_EQ(4, found0.front().block_extent.block_end);
167	found0.pop_front();
168	ASSERT_EQ(e1, found0.front().log_entry);
169	ASSERT_EQ(4, found0.front().block_extent.block_start);
170	ASSERT_EQ(12, found0.front().block_extent.block_end);
171
172	/* 0-3 will be e0 */
173	for (int i=0; i<4; i++) {
174	TestLogMapEntries found0 = map.find_map_entries(BlockExtent(i, i + 1));
175	int numfound = found0.size();
176	ASSERT_EQ(1, numfound);
177	ASSERT_EQ(e0, found0.front().log_entry);
178	}
179
180	/* 4-11 will be e1 */
181	for (int i=4; i<12; i++) {
182	TestLogMapEntries found0 = map.find_map_entries(BlockExtent(i, i + 1));
183	int numfound = found0.size();
184	ASSERT_EQ(1, numfound);
185	ASSERT_EQ(e1, found0.front().log_entry);
186	}
187
188	map.remove_log_entry(e0);
189
190	/* 0-3 will find nothing */
191	for (int i=0; i<4; i++) {
192	TestLogMapEntries found0 = map.find_map_entries(BlockExtent(i, i + 1));
193	int numfound = found0.size();
194	ASSERT_EQ(0, numfound);
195	}
196
197	/* 4-11 will still be e1 */
198	for (int i=4; i<12; i++) {
199	TestLogMapEntries found0 = map.find_map_entries(BlockExtent(i, i + 1));
200	int numfound = found0.size();
201	ASSERT_EQ(1, numfound);
202	ASSERT_EQ(e1, found0.front().log_entry);
203	}
204
205	}
206
207	TEST_F(TestWriteLogMap, OverlapMiddle) {
208	TestLogMap map(m_cct);
209
210	auto e0 = make_shared<TestLogEntry>(0, 1);
211	map.add_log_entry(e0);
212
213	TestLogMapEntries found0 = map.find_map_entries(BlockExtent(0, 1));
214	int numfound = found0.size();
215	ASSERT_EQ(1, numfound);
216	ASSERT_EQ(e0, found0.front().log_entry);
217	TestLogEntries entries = map.find_log_entries(BlockExtent(0, 1));
218	int entriesfound = entries.size();
219	ASSERT_EQ(1, entriesfound);
220	ASSERT_EQ(e0, entries.front());
221
222	auto e1 = make_shared<TestLogEntry>(1, 1);
223	map.add_log_entry(e1);
224
225	found0 = map.find_map_entries(BlockExtent(1, 2));
226	numfound = found0.size();
227	ASSERT_EQ(1, numfound);
228	ASSERT_EQ(e1, found0.front().log_entry);
229	entries = map.find_log_entries(BlockExtent(1, 2));
230	entriesfound = entries.size();
231	ASSERT_EQ(1, entriesfound);
232	ASSERT_EQ(e1, entries.front());
233
234	auto e2 = make_shared<TestLogEntry>(2, 1);
235	map.add_log_entry(e2);
236
237	found0 = map.find_map_entries(BlockExtent(2, 3));
238	numfound = found0.size();
239	ASSERT_EQ(1, numfound);
240	ASSERT_EQ(e2, found0.front().log_entry);
241	entries = map.find_log_entries(BlockExtent(2, 3));
242	entriesfound = entries.size();
243	ASSERT_EQ(1, entriesfound);
244	ASSERT_EQ(e2, entries.front());
245
246	/* replaces e1 */
247	auto e3 = make_shared<TestLogEntry>(1, 1);
248	map.add_log_entry(e3);
249
250	found0 = map.find_map_entries(BlockExtent(1, 2));
251	numfound = found0.size();
252	ASSERT_EQ(1, numfound);
253	ASSERT_EQ(e3, found0.front().log_entry);
254	entries = map.find_log_entries(BlockExtent(1, 2));
255	entriesfound = entries.size();
256	ASSERT_EQ(1, entriesfound);
257	ASSERT_EQ(e3, entries.front());
258
259	found0 = map.find_map_entries(BlockExtent(0, 100));
260	numfound = found0.size();
261	ASSERT_EQ(3, numfound);
262	ASSERT_EQ(e0, found0.front().log_entry);
263	found0.pop_front();
264	ASSERT_EQ(e3, found0.front().log_entry);
265	found0.pop_front();
266	ASSERT_EQ(e2, found0.front().log_entry);
267	entries = map.find_log_entries(BlockExtent(0, 100));
268	entriesfound = entries.size();
269	ASSERT_EQ(3, entriesfound);
270	ASSERT_EQ(e0, entries.front());
271	entries.pop_front();
272	ASSERT_EQ(e3, entries.front());
273	entries.pop_front();
274	ASSERT_EQ(e2, entries.front());
275
276	entries.clear();
277	entries.emplace_back(e0);
278	entries.emplace_back(e1);
279	map.remove_log_entries(entries);
280
281	found0 = map.find_map_entries(BlockExtent(0, 100));
282	numfound = found0.size();
283	ASSERT_EQ(2, numfound);
284	ASSERT_EQ(e3, found0.front().log_entry);
285	found0.pop_front();
286	ASSERT_EQ(e2, found0.front().log_entry);
287	}
288
289	TEST_F(TestWriteLogMap, OverlapSplit) {
290	TestLogMap map(m_cct);
291
292	auto e0 = make_shared<TestLogEntry>(0, 8);
293	map.add_log_entry(e0);
294
295	/* Splits e0 at 1 */
296	auto e1 = make_shared<TestLogEntry>(1, 1);
297	map.add_log_entry(e1);
298
299	/* Splits e0 again at 4 */
300	auto e2 = make_shared<TestLogEntry>(4, 2);
301	map.add_log_entry(e2);
302
303	/* Replaces one block of e2, and one of e0 */
304	auto e3 = make_shared<TestLogEntry>(5, 2);
305	map.add_log_entry(e3);
306
307	/* Expecting: 0:e0, 1:e1, 2..3:e0, 4:e2, 5..6:e3, 7:e0 */
308	TestLogMapEntries found0 = map.find_map_entries(BlockExtent(0, 100));
309	int numfound = found0.size();
310	ASSERT_EQ(6, numfound);
311	ASSERT_EQ(e0, found0.front().log_entry);
312	ASSERT_EQ(0, found0.front().block_extent.block_start);
313	ASSERT_EQ(1, found0.front().block_extent.block_end);
314	found0.pop_front();
315	ASSERT_EQ(e1, found0.front().log_entry);
316	ASSERT_EQ(1, found0.front().block_extent.block_start);
317	ASSERT_EQ(2, found0.front().block_extent.block_end);
318	found0.pop_front();
319	ASSERT_EQ(e0, found0.front().log_entry);
320	ASSERT_EQ(2, found0.front().block_extent.block_start);
321	ASSERT_EQ(4, found0.front().block_extent.block_end);
322	found0.pop_front();
323	ASSERT_EQ(e2, found0.front().log_entry);
324	ASSERT_EQ(4, found0.front().block_extent.block_start);
325	ASSERT_EQ(5, found0.front().block_extent.block_end);
326	found0.pop_front();
327	ASSERT_EQ(e3, found0.front().log_entry);
328	ASSERT_EQ(5, found0.front().block_extent.block_start);
329	ASSERT_EQ(7, found0.front().block_extent.block_end);
330	found0.pop_front();
331	ASSERT_EQ(e0, found0.front().log_entry);
332	ASSERT_EQ(7, found0.front().block_extent.block_start);
333	ASSERT_EQ(8, found0.front().block_extent.block_end);
334	}
335
336	} // namespace pwl
337	} // namespace cache
338	} // namespace librbd