[ceph.git] / ceph / src / test / common / test_mclock_priority_queue.cc

// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
// vim: ts=8 sw=2 smarttab
/*
 * Ceph - scalable distributed file system
 *
 * Copyright (C) 2017 Red Hat Inc.
 *
 * This is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License version 2.1, as published by the Free Software
 * Foundation.  See file COPYING.
 *
 */

#include <thread>
#include <chrono>
#include <iostream>
#include "gtest/gtest.h"
#include "common/mClockPriorityQueue.h"


struct Request {
  int value;
  Request() :
    value(0)
  {}
  Request(const Request& o) = default;
  explicit Request(int value) :
    value(value)
  {}
};


struct Client {
  int client_num;
  Client() :
    Client(-1)
  {}
  Client(int client_num) :
    client_num(client_num)
  {}
  friend bool operator<(const Client& r1, const Client& r2) {
    return r1.client_num < r2.client_num;
  }
  friend bool operator==(const Client& r1, const Client& r2) {
    return r1.client_num == r2.client_num;
  }
};


const crimson::dmclock::ClientInfo* client_info_func(const Client& c) {
  static const crimson::dmclock::ClientInfo
    the_info(10.0, 10.0, 10.0);
  return &the_info;
}


TEST(mClockPriorityQueue, Create)
{
  ceph::mClockQueue<Request,Client> q(&client_info_func);
}


TEST(mClockPriorityQueue, Sizes)
{
  ceph::mClockQueue<Request,Client> q(&client_info_func);

  ASSERT_TRUE(q.empty());
  ASSERT_EQ(0u, q.get_size_slow());

  Client c1(1);
  Client c2(2);

  q.enqueue_strict(c1, 1, Request(1));
  q.enqueue_strict(c2, 2, Request(2));
  q.enqueue_strict(c1, 2, Request(3));
  q.enqueue(c2, 1, 1u, Request(4));
  q.enqueue(c1, 2, 1u, Request(5));
  q.enqueue_strict(c2, 1, Request(6));

  ASSERT_FALSE(q.empty());
  ASSERT_EQ(6u, q.get_size_slow());


  for (int i = 0; i < 6; ++i) {
    (void) q.dequeue();
  }

  ASSERT_TRUE(q.empty());
  ASSERT_EQ(0u, q.get_size_slow());
}


TEST(mClockPriorityQueue, JustStrict)
{
  ceph::mClockQueue<Request,Client> q(&client_info_func);

  Client c1(1);
  Client c2(2);

  q.enqueue_strict(c1, 1, Request(1));
  q.enqueue_strict(c2, 2, Request(2));
  q.enqueue_strict(c1, 2, Request(3));
  q.enqueue_strict(c2, 1, Request(4));

  Request r;

  r = q.dequeue();
  ASSERT_EQ(2, r.value);
  r = q.dequeue();
  ASSERT_EQ(3, r.value);
  r = q.dequeue();
  ASSERT_EQ(1, r.value);
  r = q.dequeue();
  ASSERT_EQ(4, r.value);
}


TEST(mClockPriorityQueue, StrictPriorities)
{
  ceph::mClockQueue<Request,Client> q(&client_info_func);

  Client c1(1);
  Client c2(2);

  q.enqueue_strict(c1, 1, Request(1));
  q.enqueue_strict(c2, 2, Request(2));
  q.enqueue_strict(c1, 3, Request(3));
  q.enqueue_strict(c2, 4, Request(4));

  Request r;

  r = q.dequeue();
  ASSERT_EQ(4, r.value);
  r = q.dequeue();
  ASSERT_EQ(3, r.value);
  r = q.dequeue();
  ASSERT_EQ(2, r.value);
  r = q.dequeue();
  ASSERT_EQ(1, r.value);
}


TEST(mClockPriorityQueue, JustNotStrict)
{
  ceph::mClockQueue<Request,Client> q(&client_info_func);

  Client c1(1);
  Client c2(2);

  // non-strict queue ignores priorites, but will divide between
  // clients evenly and maintain orders between clients
  q.enqueue(c1, 1, 1u, Request(1));
  q.enqueue(c1, 2, 1u, Request(2));
  q.enqueue(c2, 3, 1u, Request(3));
  q.enqueue(c2, 4, 1u, Request(4));

  Request r1, r2;

  r1 = q.dequeue();
  ASSERT_TRUE(1 == r1.value || 3 == r1.value);

  r2 = q.dequeue();
  ASSERT_TRUE(1 == r2.value || 3 == r2.value);

  ASSERT_NE(r1.value, r2.value);

  r1 = q.dequeue();
  ASSERT_TRUE(2 == r1.value || 4 == r1.value);

  r2 = q.dequeue();
  ASSERT_TRUE(2 == r2.value || 4 == r2.value);

  ASSERT_NE(r1.value, r2.value);
}


TEST(mClockPriorityQueue, EnqueuFront)
{
  ceph::mClockQueue<Request,Client> q(&client_info_func);

  Client c1(1);
  Client c2(2);

  // non-strict queue ignores priorites, but will divide between
  // clients evenly and maintain orders between clients
  q.enqueue(c1, 1, 1u, Request(1));
  q.enqueue(c1, 2, 1u, Request(2));
  q.enqueue(c2, 3, 1u, Request(3));
  q.enqueue(c2, 4, 1u, Request(4));
  q.enqueue_strict(c2, 6, Request(6));
  q.enqueue_strict(c1, 7, Request(7));

  std::list<Request> reqs;

  for (uint i = 0; i < 4; ++i) {
    reqs.emplace_back(q.dequeue());
  }

  for (uint i = 0; i < 4; ++i) {
    Request& r = reqs.front();
    if (r.value > 5) {
      q.enqueue_strict_front(r.value == 6 ? c2 : 1, r.value, std::move(r));
    } else {
      q.enqueue_front(r.value <= 2 ? c1 : c2, r.value, 0, std::move(r));
    }
    reqs.pop_front();
  }

  Request r;

  r = q.dequeue();
  ASSERT_EQ(7, r.value);

  r = q.dequeue();
  ASSERT_EQ(6, r.value);

  r = q.dequeue();
  ASSERT_TRUE(1 == r.value || 3 == r.value);

  r = q.dequeue();
  ASSERT_TRUE(1 == r.value || 3 == r.value);

  r = q.dequeue();
  ASSERT_TRUE(2 == r.value || 4 == r.value);

  r = q.dequeue();
  ASSERT_TRUE(2 == r.value || 4 == r.value);
}


TEST(mClockPriorityQueue, RemoveByClass)
{
  ceph::mClockQueue<Request,Client> q(&client_info_func);

  Client c1(1);
  Client c2(2);
  Client c3(3);

  q.enqueue(c1, 1, 1u, Request(1));
  q.enqueue(c2, 1, 1u, Request(2));
  q.enqueue(c3, 1, 1u, Request(4));
  q.enqueue_strict(c1, 2, Request(8));
  q.enqueue_strict(c2, 1, Request(16));
  q.enqueue_strict(c3, 3, Request(32));
  q.enqueue(c3, 1, 1u, Request(64));
  q.enqueue(c2, 1, 1u, Request(128));
  q.enqueue(c1, 1, 1u, Request(256));

  int out_mask = 2 | 16 | 128;
  int in_mask = 1 | 8 | 256;

  std::list<Request> out;
  q.remove_by_class(c2, &out);

  ASSERT_EQ(3u, out.size());
  while (!out.empty()) {
    ASSERT_TRUE((out.front().value & out_mask) > 0) <<
      "had value that was not expected after first removal";
    out.pop_front();
  }

  ASSERT_EQ(6u, q.get_size_slow()) << "after removal of three from client c2";

  q.remove_by_class(c3);

  ASSERT_EQ(3u, q.get_size_slow()) << "after removal of three from client c3";
  while (!q.empty()) {
    Request r = q.dequeue();
    ASSERT_TRUE((r.value & in_mask) > 0) <<
      "had value that was not expected after two removals";
  }
}


TEST(mClockPriorityQueue, RemoveByFilter)
{
  ceph::mClockQueue<Request,Client> q(&client_info_func);

  Client c1(1);
  Client c2(2);
  Client c3(3);

  q.enqueue(c1, 1, 1u, Request(1));
  q.enqueue(c2, 1, 1u, Request(2));
  q.enqueue(c3, 1, 1u, Request(3));
  q.enqueue_strict(c1, 2, Request(4));
  q.enqueue_strict(c2, 1, Request(5));
  q.enqueue_strict(c3, 3, Request(6));
  q.enqueue(c3, 1, 1u, Request(7));
  q.enqueue(c2, 1, 1u, Request(8));
  q.enqueue(c1, 1, 1u, Request(9));

  std::list<Request> filtered;

  q.remove_by_filter([&](const Request& r) -> bool {
    if (r.value & 2) {
      filtered.push_back(r);
      return true;
    } else {
      return false;
    }
  });

  ASSERT_EQ(4u, filtered.size()) <<
    "filter should have removed four elements";
  while (!filtered.empty()) {
    ASSERT_TRUE((filtered.front().value & 2) > 0) <<
      "expect this value to have been filtered out";
    filtered.pop_front();
  }

  ASSERT_EQ(5u, q.get_size_slow()) <<
    "filter should have left five remaining elements";
  while (!q.empty()) {
    Request r = q.dequeue();
    ASSERT_TRUE((r.value & 2) == 0) <<
      "expect this value to have been left in";
   }
}
Commit	Line	Data
224ce89b WB	1	// -- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t --
	2	// vim: ts=8 sw=2 smarttab
	3	/*
	4	* Ceph - scalable distributed file system
	5	*
	6	* Copyright (C) 2017 Red Hat Inc.
	7	*
	8	* This is free software; you can redistribute it and/or
	9	* modify it under the terms of the GNU Lesser General Public
	10	* License version 2.1, as published by the Free Software
	11	* Foundation. See file COPYING.
	12	*
	13	*/
	14
	15	#include <thread>
	16	#include <chrono>
	17	#include <iostream>
	18	#include "gtest/gtest.h"
	19	#include "common/mClockPriorityQueue.h"
	20
	21
	22	struct Request {
	23	int value;
11fdf7f2 TL	24	Request() :
	25	value(0)
	26	{}
224ce89b	27	Request(const Request& o) = default;
11fdf7f2	28	explicit Request(int value) :
224ce89b WB	29	value(value)
	30	{}
	31	};
	32
	33
	34	struct Client {
	35	int client_num;
	36	Client() :
	37	Client(-1)
	38	{}
	39	Client(int client_num) :
	40	client_num(client_num)
	41	{}
	42	friend bool operator<(const Client& r1, const Client& r2) {
	43	return r1.client_num < r2.client_num;
	44	}
	45	friend bool operator==(const Client& r1, const Client& r2) {
	46	return r1.client_num == r2.client_num;
	47	}
	48	};
	49
	50
11fdf7f2	51	const crimson::dmclock::ClientInfo* client_info_func(const Client& c) {
224ce89b WB	52	static const crimson::dmclock::ClientInfo
224ce89b WB	53	the_info(10.0, 10.0, 10.0);
11fdf7f2	54	return &the_info;
224ce89b WB	55	}
	56
	57
	58	TEST(mClockPriorityQueue, Create)
	59	{
	60	ceph::mClockQueue<Request,Client> q(&client_info_func);
	61	}
	62
	63
	64	TEST(mClockPriorityQueue, Sizes)
	65	{
	66	ceph::mClockQueue<Request,Client> q(&client_info_func);
	67
	68	ASSERT_TRUE(q.empty());
11fdf7f2	69	ASSERT_EQ(0u, q.get_size_slow());
224ce89b WB	70
	71	Client c1(1);
	72	Client c2(2);
	73
	74	q.enqueue_strict(c1, 1, Request(1));
	75	q.enqueue_strict(c2, 2, Request(2));
	76	q.enqueue_strict(c1, 2, Request(3));
11fdf7f2 TL	77	q.enqueue(c2, 1, 1u, Request(4));
11fdf7f2 TL	78	q.enqueue(c1, 2, 1u, Request(5));
224ce89b WB	79	q.enqueue_strict(c2, 1, Request(6));
	80
	81	ASSERT_FALSE(q.empty());
11fdf7f2	82	ASSERT_EQ(6u, q.get_size_slow());
224ce89b WB	83
	84
	85	for (int i = 0; i < 6; ++i) {
	86	(void) q.dequeue();
	87	}
	88
	89	ASSERT_TRUE(q.empty());
11fdf7f2	90	ASSERT_EQ(0u, q.get_size_slow());
224ce89b WB	91	}
	92
	93
	94	TEST(mClockPriorityQueue, JustStrict)
	95	{
	96	ceph::mClockQueue<Request,Client> q(&client_info_func);
	97
	98	Client c1(1);
	99	Client c2(2);
	100
	101	q.enqueue_strict(c1, 1, Request(1));
	102	q.enqueue_strict(c2, 2, Request(2));
	103	q.enqueue_strict(c1, 2, Request(3));
	104	q.enqueue_strict(c2, 1, Request(4));
	105
	106	Request r;
	107
	108	r = q.dequeue();
	109	ASSERT_EQ(2, r.value);
	110	r = q.dequeue();
	111	ASSERT_EQ(3, r.value);
	112	r = q.dequeue();
	113	ASSERT_EQ(1, r.value);
	114	r = q.dequeue();
	115	ASSERT_EQ(4, r.value);
	116	}
	117
	118
	119	TEST(mClockPriorityQueue, StrictPriorities)
	120	{
	121	ceph::mClockQueue<Request,Client> q(&client_info_func);
	122
	123	Client c1(1);
	124	Client c2(2);
	125
	126	q.enqueue_strict(c1, 1, Request(1));
	127	q.enqueue_strict(c2, 2, Request(2));
	128	q.enqueue_strict(c1, 3, Request(3));
	129	q.enqueue_strict(c2, 4, Request(4));
	130
	131	Request r;
	132
	133	r = q.dequeue();
	134	ASSERT_EQ(4, r.value);
	135	r = q.dequeue();
	136	ASSERT_EQ(3, r.value);
	137	r = q.dequeue();
	138	ASSERT_EQ(2, r.value);
	139	r = q.dequeue();
	140	ASSERT_EQ(1, r.value);
	141	}
	142
	143
	144	TEST(mClockPriorityQueue, JustNotStrict)
	145	{
	146	ceph::mClockQueue<Request,Client> q(&client_info_func);
	147
	148	Client c1(1);
	149	Client c2(2);
	150
	151	// non-strict queue ignores priorites, but will divide between
	152	// clients evenly and maintain orders between clients
11fdf7f2 TL	153	q.enqueue(c1, 1, 1u, Request(1));
	154	q.enqueue(c1, 2, 1u, Request(2));
	155	q.enqueue(c2, 3, 1u, Request(3));
	156	q.enqueue(c2, 4, 1u, Request(4));
224ce89b WB	157
	158	Request r1, r2;
	159
	160	r1 = q.dequeue();
	161	ASSERT_TRUE(1 == r1.value \|\| 3 == r1.value);
	162
	163	r2 = q.dequeue();
	164	ASSERT_TRUE(1 == r2.value \|\| 3 == r2.value);
	165
	166	ASSERT_NE(r1.value, r2.value);
	167
	168	r1 = q.dequeue();
	169	ASSERT_TRUE(2 == r1.value \|\| 4 == r1.value);
	170
	171	r2 = q.dequeue();
	172	ASSERT_TRUE(2 == r2.value \|\| 4 == r2.value);
	173
	174	ASSERT_NE(r1.value, r2.value);
	175	}
	176
	177
	178	TEST(mClockPriorityQueue, EnqueuFront)
	179	{
	180	ceph::mClockQueue<Request,Client> q(&client_info_func);
	181
	182	Client c1(1);
	183	Client c2(2);
	184
	185	// non-strict queue ignores priorites, but will divide between
	186	// clients evenly and maintain orders between clients
11fdf7f2 TL	187	q.enqueue(c1, 1, 1u, Request(1));
	188	q.enqueue(c1, 2, 1u, Request(2));
	189	q.enqueue(c2, 3, 1u, Request(3));
	190	q.enqueue(c2, 4, 1u, Request(4));
224ce89b WB	191	q.enqueue_strict(c2, 6, Request(6));
	192	q.enqueue_strict(c1, 7, Request(7));
	193
	194	std::list<Request> reqs;
	195
	196	for (uint i = 0; i < 4; ++i) {
	197	reqs.emplace_back(q.dequeue());
	198	}
	199
	200	for (uint i = 0; i < 4; ++i) {
	201	Request& r = reqs.front();
	202	if (r.value > 5) {
11fdf7f2	203	q.enqueue_strict_front(r.value == 6 ? c2 : 1, r.value, std::move(r));
224ce89b	204	} else {
11fdf7f2	205	q.enqueue_front(r.value <= 2 ? c1 : c2, r.value, 0, std::move(r));
224ce89b WB	206	}
	207	reqs.pop_front();
	208	}
	209
	210	Request r;
	211
	212	r = q.dequeue();
	213	ASSERT_EQ(7, r.value);
	214
	215	r = q.dequeue();
	216	ASSERT_EQ(6, r.value);
	217
	218	r = q.dequeue();
	219	ASSERT_TRUE(1 == r.value \|\| 3 == r.value);
	220
	221	r = q.dequeue();
	222	ASSERT_TRUE(1 == r.value \|\| 3 == r.value);
	223
	224	r = q.dequeue();
	225	ASSERT_TRUE(2 == r.value \|\| 4 == r.value);
	226
	227	r = q.dequeue();
	228	ASSERT_TRUE(2 == r.value \|\| 4 == r.value);
	229	}
	230
	231
	232	TEST(mClockPriorityQueue, RemoveByClass)
	233	{
	234	ceph::mClockQueue<Request,Client> q(&client_info_func);
	235
	236	Client c1(1);
	237	Client c2(2);
	238	Client c3(3);
	239
11fdf7f2 TL	240	q.enqueue(c1, 1, 1u, Request(1));
	241	q.enqueue(c2, 1, 1u, Request(2));
	242	q.enqueue(c3, 1, 1u, Request(4));
224ce89b WB	243	q.enqueue_strict(c1, 2, Request(8));
	244	q.enqueue_strict(c2, 1, Request(16));
	245	q.enqueue_strict(c3, 3, Request(32));
11fdf7f2 TL	246	q.enqueue(c3, 1, 1u, Request(64));
	247	q.enqueue(c2, 1, 1u, Request(128));
	248	q.enqueue(c1, 1, 1u, Request(256));
224ce89b WB	249
	250	int out_mask = 2 \| 16 \| 128;
	251	int in_mask = 1 \| 8 \| 256;
	252
	253	std::list<Request> out;
	254	q.remove_by_class(c2, &out);
	255
	256	ASSERT_EQ(3u, out.size());
	257	while (!out.empty()) {
	258	ASSERT_TRUE((out.front().value & out_mask) > 0) <<
	259	"had value that was not expected after first removal";
	260	out.pop_front();
	261	}
	262
11fdf7f2	263	ASSERT_EQ(6u, q.get_size_slow()) << "after removal of three from client c2";
224ce89b WB	264
	265	q.remove_by_class(c3);
	266
11fdf7f2	267	ASSERT_EQ(3u, q.get_size_slow()) << "after removal of three from client c3";
224ce89b WB	268	while (!q.empty()) {
	269	Request r = q.dequeue();
	270	ASSERT_TRUE((r.value & in_mask) > 0) <<
	271	"had value that was not expected after two removals";
	272	}
	273	}
	274
	275
	276	TEST(mClockPriorityQueue, RemoveByFilter)
	277	{
	278	ceph::mClockQueue<Request,Client> q(&client_info_func);
	279
	280	Client c1(1);
	281	Client c2(2);
	282	Client c3(3);
	283
11fdf7f2 TL	284	q.enqueue(c1, 1, 1u, Request(1));
	285	q.enqueue(c2, 1, 1u, Request(2));
	286	q.enqueue(c3, 1, 1u, Request(3));
224ce89b WB	287	q.enqueue_strict(c1, 2, Request(4));
	288	q.enqueue_strict(c2, 1, Request(5));
	289	q.enqueue_strict(c3, 3, Request(6));
11fdf7f2 TL	290	q.enqueue(c3, 1, 1u, Request(7));
	291	q.enqueue(c2, 1, 1u, Request(8));
	292	q.enqueue(c1, 1, 1u, Request(9));
224ce89b WB	293
	294	std::list<Request> filtered;
	295
	296	q.remove_by_filter([&](const Request& r) -> bool {
	297	if (r.value & 2) {
	298	filtered.push_back(r);
	299	return true;
	300	} else {
	301	return false;
	302	}
	303	});
	304
	305	ASSERT_EQ(4u, filtered.size()) <<
	306	"filter should have removed four elements";
	307	while (!filtered.empty()) {
	308	ASSERT_TRUE((filtered.front().value & 2) > 0) <<
	309	"expect this value to have been filtered out";
	310	filtered.pop_front();
	311	}
	312
11fdf7f2	313	ASSERT_EQ(5u, q.get_size_slow()) <<
224ce89b WB	314	"filter should have left five remaining elements";
	315	while (!q.empty()) {
	316	Request r = q.dequeue();
	317	ASSERT_TRUE((r.value & 2) == 0) <<
	318	"expect this value to have been left in";
	319	}
	320	}