ceph/src/test/common/test_lru.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) 2014 Cloudwatt <libre.licensing@cloudwatt.com>
   7  *
   8  * Author: Sahid Orentino Ferdjaoui <sahid.ferdjaoui@cloudwatt.com>
   9  *
  10  *  This library is free software; you can redistribute it and/or
  11  *  modify it under the terms of the GNU Lesser General Public
  12  *  License as published by the Free Software Foundation; either
  13  *  version 2.1 of the License, or (at your option) any later version.
  14  *
  15  */
  16
  17 #include <errno.h>
  18 #include <gtest/gtest.h>
  19
  20 #include "include/lru.h"
  21
  22
  23 class Item : public LRUObject {
  24 public:
  25   int id;
  26   Item() : id(0) {}
  27   Item(int i) : id(i) {}
  28   void set(int i) {id = i;}
  29 };
  30
  31
  32 TEST(lru, InsertTop) {
  33   LRU lru;
  34   static const int n = 100;
  35   Item items[n];
  36
  37   lru.lru_set_midpoint(.5); // 50% of elements.
  38   for (int i=0; i<n; i++) {
  39     items[i].set(i);
  40     lru.lru_insert_top(&items[i]);
  41   }
  42   ASSERT_EQ(50U, lru.lru_get_top());
  43   ASSERT_EQ(50U, lru.lru_get_bot());
  44   ASSERT_EQ(100U, lru.lru_get_size());
  45
  46   ASSERT_EQ(0, (static_cast<Item*>(lru.lru_expire()))->id);
  47 }
  48
  49 TEST(lru, InsertMid) {
  50   LRU lru;
  51   static const int n = 102;
  52   Item items[n];
  53
  54   lru.lru_set_midpoint(.7); // 70% of elements.
  55   for (int i=0; i<n; i++) {
  56     items[i].set(i);
  57     lru.lru_insert_mid(&items[i]);
  58   }
  59   ASSERT_EQ(71U, lru.lru_get_top());
  60   ASSERT_EQ(31U, lru.lru_get_bot());
  61   ASSERT_EQ(102U, lru.lru_get_size());
  62
  63   ASSERT_EQ(0, (static_cast<Item*>(lru.lru_expire()))->id);
  64 }
  65
  66 TEST(lru, InsertBot) {
  67   LRU lru;
  68   static const int n = 100;
  69   Item items[n];
  70
  71   lru.lru_set_midpoint(.7); // 70% of elements.
  72   for (int i=0; i<n; i++) {
  73     items[i].set(i);
  74     lru.lru_insert_bot(&items[i]);
  75   }
  76   ASSERT_EQ(70U, lru.lru_get_top());
  77   ASSERT_EQ(30U, lru.lru_get_bot());
  78   ASSERT_EQ(100U, lru.lru_get_size());
  79
  80   ASSERT_EQ(99, (static_cast<Item*>(lru.lru_expire()))->id);
  81 }
  82
  83 TEST(lru, Adjust) {
  84   LRU lru;
  85   static const int n = 100;
  86   Item items[n];
  87
  88   lru.lru_set_midpoint(.6); // 60% of elements.
  89   for (int i=0; i<n; i++) {
  90     items[i].set(i);
  91     lru.lru_insert_top(&items[i]);
  92     if (i % 5 == 0)
  93       items[i].lru_pin();
  94   }
  95   ASSERT_EQ(48U, lru.lru_get_top()); /* 60% of unpinned */
  96   ASSERT_EQ(52U, lru.lru_get_bot());
  97   ASSERT_EQ(100U, lru.lru_get_size());
  98
  99   ASSERT_EQ(1, (static_cast<Item*>(lru.lru_expire()))->id);
 100   ASSERT_EQ(1U, lru.lru_get_pintail());
 101   ASSERT_EQ(47U, lru.lru_get_top()); /* 60% of unpinned */
 102   ASSERT_EQ(51U, lru.lru_get_bot());
 103   ASSERT_EQ(99U, lru.lru_get_size());
 104   ASSERT_EQ(2, (static_cast<Item*>(lru.lru_expire()))->id);
 105   ASSERT_EQ(1U, lru.lru_get_pintail());
 106   ASSERT_EQ(46U, lru.lru_get_top()); /* 60% of unpinned */
 107   ASSERT_EQ(51U, lru.lru_get_bot());
 108   ASSERT_EQ(98U, lru.lru_get_size());
 109   ASSERT_EQ(3, (static_cast<Item*>(lru.lru_expire()))->id);
 110   ASSERT_EQ(4, (static_cast<Item*>(lru.lru_expire()))->id);
 111   ASSERT_EQ(6, (static_cast<Item*>(lru.lru_expire()))->id);
 112   ASSERT_EQ(2U, lru.lru_get_pintail());
 113   ASSERT_EQ(45U, lru.lru_get_top()); /* 60% of unpinned */
 114   ASSERT_EQ(48U, lru.lru_get_bot());
 115   ASSERT_EQ(95U, lru.lru_get_size());
 116 }
 117
 118 TEST(lru, Pinning) {
 119   LRU lru;
 120
 121   Item ob0(0), ob1(1);
 122
 123   // test before ob1 are in a LRU
 124   ob1.lru_pin();
 125   ASSERT_FALSE(ob1.lru_is_expireable());
 126
 127   ob1.lru_unpin();
 128   ASSERT_TRUE(ob1.lru_is_expireable());
 129
 130   // test when ob1 are in a LRU
 131   lru.lru_insert_top(&ob0);
 132   lru.lru_insert_top(&ob1);
 133
 134   ob1.lru_pin();
 135   ob1.lru_pin(); // Verify that, one incr.
 136   ASSERT_EQ(1U, lru.lru_get_num_pinned());
 137   ASSERT_FALSE(ob1.lru_is_expireable());
 138
 139   ob1.lru_unpin();
 140   ob1.lru_unpin(); // Verify that, one decr.
 141   ASSERT_EQ(0U, lru.lru_get_num_pinned());
 142   ASSERT_TRUE(ob1.lru_is_expireable());
 143
 144   ASSERT_EQ(0, (static_cast<Item*>(lru.lru_expire()))->id);
 145   ob0.lru_pin();
 146   ASSERT_EQ(1, (static_cast<Item*>(lru.lru_expire()))->id);
 147 }
 148
 149
 150 /*
 151  * Local Variables:
 152  * compile-command: "cd ../.. ; make -j4 &&
 153  *   make unittest_lru &&
 154  *   valgrind --tool=memcheck --leak-check=full \
 155  *      ./unittest_lru
 156  *   "
 157  * End:
 158  */