ceph/src/test/common/test_mclock_priority_queue.cc

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