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     adjust();
 161     // look through tail of bot
 162     while (bottom.size()) {
 163       LRUObject *p = bottom.back();
 164       if (!p->lru_pinned) return p;
 165
 166       // move to pintail
 167       pintail.push_front(&p->lru_link);
 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     }
 178
 179     // no luck!
 180     return NULL;
 181   }
 182
 183   LRUObject *lru_expire() {
 184     LRUObject *p = lru_get_next_expire();
 185     if (p)
 186       return lru_remove(p);
 187     return NULL;
 188   }
 189
 190   void lru_status() {
 191     //generic_dout(10) << "lru: " << lru_get_size() << " items, " << top.size() << " top, " << bottom.size() << " bot, " << pintail.size() << " pintail" << dendl;
 192   }
 193
 194 protected:
 195   // adjust top/bot balance, as necessary
 196   void adjust() {
 197     uint64_t toplen = top.size();
 198     uint64_t topwant = (midpoint * (double)(lru_get_size() - num_pinned));
 199     /* move items from below midpoint (bottom) to top: move midpoint forward */
 200     for (uint64_t i = toplen; i < topwant; i++) {
 201       top.push_back(&bottom.front()->lru_link);
 202     }
 203     /* or: move items from above midpoint (top) to bottom: move midpoint backwards */
 204     for (uint64_t i = toplen; i > topwant; i--) {
 205       bottom.push_front(&top.back()->lru_link);
 206     }
 207   }
 208
 209   uint64_t num_pinned;
 210   double midpoint;
 211
 212   friend class LRUObject;
 213 private:
 214   typedef xlist<LRUObject *> LRUList;
 215   LRUList top, bottom, pintail;
 216 };
 217
 218 inline LRUObject::~LRUObject() {
 219   if (lru) {
 220     lru->lru_remove(this);
 221   }
 222 }
 223
 224 inline void LRUObject::lru_pin() {
 225   if (lru && !lru_pinned) {
 226     lru->num_pinned++;
 227   }
 228   lru_pinned = true;
 229 }
 230
 231 inline void LRUObject::lru_unpin() {
 232   if (lru && lru_pinned) {
 233     lru->num_pinned--;
 234
 235     // move from pintail -> bot
 236     if (lru_link.get_list() == &lru->pintail) {
 237       lru->lru_bottouch(this);
 238     }
 239   }
 240   lru_pinned = false;
 241 }
 242
 243 #endif