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 <stdint.h>
  21
  22 #include "common/config.h"
  23
  24
  25
  26 class LRUObject {
  27  private:
  28   LRUObject *lru_next, *lru_prev;
  29   bool lru_pinned;
  30   class LRU *lru;
  31   class LRUList *lru_list;
  32
  33  public:
  34   LRUObject() {
  35     lru_next = lru_prev = NULL;
  36     lru_list = 0;
  37     lru_pinned = false;
  38     lru = 0;
  39   }
  40
  41   // pin/unpin item in cache
  42   void lru_pin();
  43   void lru_unpin();
  44   bool lru_is_expireable() const { return !lru_pinned; }
  45
  46   friend class LRU;
  47   friend class LRUList;
  48 };
  49
  50
  51 class LRUList {
  52  private:
  53   LRUObject *head, *tail;
  54   uint32_t len;
  55
  56  public:
  57   LRUList() {
  58     head = tail = 0;
  59     len = 0;
  60   }
  61
  62   uint32_t  get_length() const { return len; }
  63
  64   LRUObject *get_head() {
  65     return head;
  66   }
  67   LRUObject *get_tail() {
  68     return tail;
  69   }
  70
  71   void clear() {
  72     while (len > 0) {
  73       remove(get_head());
  74     }
  75   }
  76
  77   void insert_head(LRUObject *o) {
  78     o->lru_next = head;
  79     o->lru_prev = NULL;
  80     if (head) {
  81       head->lru_prev = o;
  82     } else {
  83       tail = o;
  84     }
  85     head = o;
  86     o->lru_list = this;
  87     len++;
  88   }
  89   void insert_tail(LRUObject *o) {
  90     o->lru_next = NULL;
  91     o->lru_prev = tail;
  92     if (tail) {
  93       tail->lru_next = o;
  94     } else {
  95       head = o;
  96     }
  97     tail = o;
  98     o->lru_list = this;
  99     len++;
 100   }
 101
 102   void remove(LRUObject *o) {
 103     assert(o->lru_list == this);
 104     if (o->lru_next)
 105       o->lru_next->lru_prev = o->lru_prev;
 106     else
 107       tail = o->lru_prev;
 108     if (o->lru_prev)
 109       o->lru_prev->lru_next = o->lru_next;
 110     else
 111       head = o->lru_next;
 112     o->lru_next = o->lru_prev = NULL;
 113     o->lru_list = 0;
 114     assert(len>0);
 115     len--;
 116   }
 117
 118 };
 119
 120
 121 class LRU {
 122  protected:
 123   LRUList lru_top, lru_bot, lru_pintail;
 124   uint32_t lru_num, lru_num_pinned;
 125   uint32_t lru_max;   // max items
 126   double lru_midpoint;
 127
 128   friend class LRUObject;
 129   //friend class MDCache; // hack
 130
 131  public:
 132   LRU(int max = 0) {
 133     lru_num = 0;
 134     lru_num_pinned = 0;
 135     lru_midpoint = .6;
 136     lru_max = max;
 137   }
 138
 139   uint32_t lru_get_size() const { return lru_num; }
 140   uint32_t lru_get_top() const { return lru_top.get_length(); }
 141   uint32_t lru_get_bot() const{ return lru_bot.get_length(); }
 142   uint32_t lru_get_pintail() const { return lru_pintail.get_length(); }
 143   uint32_t lru_get_max() const { return lru_max; }
 144   uint32_t lru_get_num_pinned() const { return lru_num_pinned; }
 145
 146   void lru_set_max(uint32_t m) { lru_max = m; }
 147   void lru_set_midpoint(float f) { lru_midpoint = f; }
 148
 149   void lru_clear() {
 150     lru_top.clear();
 151     lru_bot.clear();
 152     lru_pintail.clear();
 153     lru_num = 0;
 154   }
 155
 156   // insert at top of lru
 157   void lru_insert_top(LRUObject *o) {
 158     //assert(!o->lru_in_lru);
 159     //o->lru_in_lru = true;
 160     assert(!o->lru);
 161     o->lru = this;
 162     lru_top.insert_head( o );
 163     lru_num++;
 164     if (o->lru_pinned) lru_num_pinned++;
 165     lru_adjust();
 166   }
 167
 168   // insert at mid point in lru
 169   void lru_insert_mid(LRUObject *o) {
 170     //assert(!o->lru_in_lru);
 171     //o->lru_in_lru = true;
 172     assert(!o->lru);
 173     o->lru = this;
 174     lru_bot.insert_head(o);
 175     lru_num++;
 176     if (o->lru_pinned) lru_num_pinned++;
 177   }
 178
 179   // insert at bottom of lru
 180   void lru_insert_bot(LRUObject *o) {
 181     assert(!o->lru);
 182     o->lru = this;
 183     lru_bot.insert_tail(o);
 184     lru_num++;
 185     if (o->lru_pinned) lru_num_pinned++;
 186   }
 187
 188   /*
 189   // insert at bottom of lru
 190   void lru_insert_pintail(LRUObject *o) {
 191     assert(!o->lru);
 192     o->lru = this;
 193
 194     assert(o->lru_pinned);
 195
 196     lru_pintail.insert_head(o);
 197     lru_num++;
 198     lru_num_pinned += o->lru_pinned;
 199   }
 200   */
 201
 202
 203
 204
 205   // adjust top/bot balance, as necessary
 206   void lru_adjust() {
 207     if (!lru_max) return;
 208
 209     unsigned toplen = lru_top.get_length();
 210     unsigned topwant = (unsigned)(lru_midpoint * ((double)lru_max - lru_num_pinned));
 211     while (toplen > 0 &&
 212            toplen > topwant) {
 213       // remove from tail of top, stick at head of bot
 214       // FIXME: this could be way more efficient by moving a whole chain of items.
 215
 216       LRUObject *o = lru_top.get_tail();
 217       lru_top.remove(o);
 218       lru_bot.insert_head(o);
 219       toplen--;
 220     }
 221   }
 222
 223
 224   // remove an item
 225   LRUObject *lru_remove(LRUObject *o) {
 226     // not in list
 227     //assert(o->lru_in_lru);
 228     //if (!o->lru_in_lru) return o;  // might have expired and been removed that way.
 229     if (!o->lru) return o;
 230
 231     assert((o->lru_list == &lru_pintail) ||
 232            (o->lru_list == &lru_top) ||
 233            (o->lru_list == &lru_bot));
 234     o->lru_list->remove(o);
 235
 236     lru_num--;
 237     if (o->lru_pinned) lru_num_pinned--;
 238     o->lru = 0;
 239     return o;
 240   }
 241
 242   // touch item -- move to head of lru
 243   bool lru_touch(LRUObject *o) {
 244     lru_remove(o);
 245     lru_insert_top(o);
 246     return true;
 247   }
 248
 249   // touch item -- move to midpoint (unless already higher)
 250   bool lru_midtouch(LRUObject *o) {
 251     if (o->lru_list == &lru_top) return false;
 252
 253     lru_remove(o);
 254     lru_insert_mid(o);
 255     return true;
 256   }
 257
 258   // touch item -- move to bottom
 259   bool lru_bottouch(LRUObject *o) {
 260     lru_remove(o);
 261     lru_insert_bot(o);
 262     return true;
 263   }
 264
 265   void lru_touch_entire_pintail() {
 266     // promote entire pintail to the top lru
 267     while (lru_pintail.get_length() > 0) {
 268       LRUObject *o = lru_pintail.get_head();
 269       lru_pintail.remove(o);
 270       lru_top.insert_tail(o);
 271     }
 272   }
 273
 274
 275   // expire -- expire a single item
 276   LRUObject *lru_get_next_expire() {
 277     LRUObject *p;
 278
 279     // look through tail of bot
 280     while (lru_bot.get_length()) {
 281       p = lru_bot.get_tail();
 282       if (!p->lru_pinned) return p;
 283
 284       // move to pintail
 285       lru_bot.remove(p);
 286       lru_pintail.insert_head(p);
 287     }
 288
 289     // ok, try head then
 290     while (lru_top.get_length()) {
 291       p = lru_top.get_tail();
 292       if (!p->lru_pinned) return p;
 293
 294       // move to pintail
 295       lru_top.remove(p);
 296       lru_pintail.insert_head(p);
 297     }
 298
 299     // no luck!
 300     return NULL;
 301   }
 302
 303   LRUObject *lru_expire() {
 304     LRUObject *p = lru_get_next_expire();
 305     if (p)
 306       return lru_remove(p);
 307     return NULL;
 308   }
 309
 310
 311   void lru_status() {
 312     //generic_dout(10) << "lru: " << lru_num << " items, " << lru_top.get_length() << " top, " << lru_bot.get_length() << " bot, " << lru_pintail.get_length() << " pintail" << dendl;
 313   }
 314
 315 };
 316
 317
 318 inline void LRUObject::lru_pin() {
 319   if (lru && !lru_pinned) {
 320     lru->lru_num_pinned++;
 321     lru->lru_adjust();
 322   }
 323   lru_pinned = true;
 324 }
 325
 326 inline void LRUObject::lru_unpin() {
 327   if (lru && lru_pinned) {
 328     lru->lru_num_pinned--;
 329
 330     // move from pintail -> bot
 331     if (lru_list == &lru->lru_pintail) {
 332       lru->lru_pintail.remove(this);
 333       lru->lru_bot.insert_tail(this);
 334     }
 335     lru->lru_adjust();
 336   }
 337   lru_pinned = false;
 338 }
 339
 340 #endif