src/ceph/src/include/lru.h

   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) 2004-2006 Sage Weil <sage@newdream.net>
   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
  16
  17 #ifndef CEPH_LRU_H
  18 #define CEPH_LRU_H
  19
  20 #include <math.h>
  21 #include <stdint.h>
  22
  23 #include "common/config.h"
  24 #include "xlist.h"
  25
  26 class LRUObject {
  27 public:
  28   LRUObject() : lru(), lru_link(this), lru_pinned(false) { }
  29   ~LRUObject();
  30
  31   // pin/unpin item in cache
  32   void lru_pin();
  33   void lru_unpin();
  34   bool lru_is_expireable() const { return !lru_pinned; }
  35
  36   friend class LRU;
  37 private:
  38   class LRU *lru;
  39   xlist<LRUObject *>::item lru_link;
  40   bool lru_pinned;
  41 };
  42
  43 class LRU {
  44 public:
  45   LRU() : num_pinned(0), midpoint(0.6) {}
  46
  47   uint64_t lru_get_size() const { return lru_get_top()+lru_get_bot()+lru_get_pintail(); }
  48   uint64_t lru_get_top() const { return top.size(); }
  49   uint64_t lru_get_bot() const{ return bottom.size(); }
  50   uint64_t lru_get_pintail() const { return pintail.size(); }
  51   uint64_t lru_get_num_pinned() const { return num_pinned; }
  52
  53   void lru_set_midpoint(double f) { midpoint = fmin(1.0, fmax(0.0, f)); }
  54
  55   void lru_clear() {
  56     while (!top.empty()) {
  57       lru_remove(top.front());
  58     }
  59     while (!bottom.empty()) {
  60       lru_remove(bottom.front());
  61     }
  62     while (!pintail.empty()) {
  63       lru_remove(pintail.front());
  64     }
  65     assert(num_pinned == 0);
  66   }
  67
  68   // insert at top of lru
  69   void lru_insert_top(LRUObject *o) {
  70     assert(!o->lru);
  71     o->lru = this;
  72     top.push_front(&o->lru_link);
  73     if (o->lru_pinned) num_pinned++;
  74     adjust();
  75   }
  76
  77   // insert at mid point in lru
  78   void lru_insert_mid(LRUObject *o) {
  79     assert(!o->lru);
  80     o->lru = this;
  81     bottom.push_front(&o->lru_link);
  82     if (o->lru_pinned) num_pinned++;
  83     adjust();
  84   }
  85
  86   // insert at bottom of lru
  87   void lru_insert_bot(LRUObject *o) {
  88     assert(!o->lru);
  89     o->lru = this;
  90     bottom.push_back(&o->lru_link);
  91     if (o->lru_pinned) num_pinned++;
  92     adjust();
  93   }
  94
  95   // remove an item
  96   LRUObject *lru_remove(LRUObject *o) {
  97     if (!o->lru) return o;
  98     auto list = o->lru_link.get_list();
  99     assert(list == &top || list == &bottom || list == &pintail);
 100     o->lru_link.remove_myself();
 101     if (o->lru_pinned) num_pinned--;
 102     o->lru = nullptr;
 103     adjust();
 104     return o;
 105   }
 106
 107   // touch item -- move to head of lru
 108   bool lru_touch(LRUObject *o) {
 109     if (!o->lru) {
 110       lru_insert_top(o);
 111     } else {
 112       assert(o->lru == this);
 113       auto list = o->lru_link.get_list();
 114       assert(list == &top || list == &bottom || list == &pintail);
 115       top.push_front(&o->lru_link);
 116       adjust();
 117     }
 118     return true;
 119   }
 120
 121   // touch item -- move to midpoint (unless already higher)
 122   bool lru_midtouch(LRUObject *o) {
 123     if (!o->lru) {
 124       lru_insert_mid(o);
 125     } else {
 126       assert(o->lru == this);
 127       auto list = o->lru_link.get_list();
 128       assert(list == &top || list == &bottom || list == &pintail);
 129       if (list == &top) return false;
 130       bottom.push_front(&o->lru_link);
 131       adjust();
 132     }
 133     return true;
 134   }
 135
 136   // touch item -- move to bottom
 137   bool lru_bottouch(LRUObject *o) {
 138     if (!o->lru) {
 139       lru_insert_bot(o);
 140     } else {
 141       assert(o->lru == this);
 142       auto list = o->lru_link.get_list();
 143       assert(list == &top || list == &bottom || list == &pintail);
 144       bottom.push_back(&o->lru_link);
 145       adjust();
 146     }
 147     return true;
 148   }
 149
 150   void lru_touch_entire_pintail() {
 151     // promote entire pintail to the top lru
 152     while (pintail.size() > 0) {
 153       top.push_back(&pintail.front()->lru_link);
 154       adjust();
 155     }
 156   }
 157
 158   // expire -- expire a single item
 159   LRUObject *lru_get_next_expire() {
 160     // look through tail of bot
 161     while (bottom.size()) {
 162       LRUObject *p = bottom.back();
 163       if (!p->lru_pinned) return p;
 164
 165       // move to pintail
 166       pintail.push_front(&p->lru_link);
 167       adjust();
 168     }
 169
 170     // ok, try head then
 171     while (top.size()) {
 172       LRUObject *p = top.back();
 173       if (!p->lru_pinned) return p;
 174
 175       // move to pintail
 176       pintail.push_front(&p->lru_link);
 177       adjust();
 178     }
 179
 180     // no luck!
 181     return NULL;
 182   }
 183
 184   LRUObject *lru_expire() {
 185     LRUObject *p = lru_get_next_expire();
 186     if (p)
 187       return lru_remove(p);
 188     return NULL;
 189   }
 190
 191   void lru_status() {
 192     //generic_dout(10) << "lru: " << lru_get_size() << " items, " << top.size() << " top, " << bottom.size() << " bot, " << pintail.size() << " pintail" << dendl;
 193   }
 194
 195 protected:
 196   // adjust top/bot balance, as necessary
 197   void adjust() {
 198     uint64_t toplen = top.size();
 199     uint64_t topwant = (midpoint * (double)(lru_get_size() - num_pinned));
 200     /* move items from below midpoint (bottom) to top: move midpoint forward */
 201     for (uint64_t i = toplen; i < topwant; i++) {
 202       top.push_back(&bottom.front()->lru_link);
 203     }
 204     /* or: move items from above midpoint (top) to bottom: move midpoint backwards */
 205     for (uint64_t i = toplen; i > topwant; i--) {
 206       bottom.push_front(&top.back()->lru_link);
 207     }
 208   }
 209
 210   uint64_t num_pinned;
 211   double midpoint;
 212
 213   friend class LRUObject;
 214 private:
 215   typedef xlist<LRUObject *> LRUList;
 216   LRUList top, bottom, pintail;
 217 };
 218
 219 inline LRUObject::~LRUObject() {
 220   if (lru) {
 221     lru->lru_remove(this);
 222   }
 223 }
 224
 225 inline void LRUObject::lru_pin() {
 226   if (lru && !lru_pinned) {
 227     lru->num_pinned++;
 228   }
 229   lru_pinned = true;
 230 }
 231
 232 inline void LRUObject::lru_unpin() {
 233   if (lru && lru_pinned) {
 234     lru->num_pinned--;
 235
 236     // move from pintail -> bot
 237     if (lru_link.get_list() == &lru->pintail) {
 238       lru->lru_bottouch(this);
 239     }
 240   }
 241   lru_pinned = false;
 242 }
 243
 244 #endif