lunaix-os/kernel/lrud.c

   1 #include <lunaix/ds/lru.h>
   2 #include <lunaix/mm/valloc.h>
   3 #include <lunaix/spike.h>
   4 #include <lunaix/fs/twimap.h>
   5 #include <lunaix/fs/twifs.h>
   6
   7 #include <klibc/string.h>
   8
   9 static struct llist_header zone_lead = { .next = &zone_lead, .prev = &zone_lead };
  10
  11 DEFINE_SPINLOCK_OPS(struct lru_zone*, lock);
  12
  13
  14 static void
  15 __do_evict_lockless(struct lru_zone* zone, struct llist_header* elem)
  16 {
  17     llist_delete(elem);
  18     if (!zone->try_evict(container_of(elem, struct lru_node, lru_nodes))) {
  19         // if the node is unable to evict, raise it's rank by one, so
  20         // others can have chance in the next round
  21         struct llist_header* new_tail = zone->lead_node.prev;
  22         llist_prepend(new_tail, elem);
  23     } else {
  24         zone->objects--;
  25     }
  26
  27     zone->evict_stats.n_single++;
  28 }
  29
  30 static void
  31 __lru_evict_all_lockness(struct lru_zone* zone)
  32 {
  33     struct llist_header* tail = zone->lead_node.prev;
  34     while (tail != &zone->lead_node) {
  35         __do_evict_lockless(zone, tail);
  36         tail = tail->prev;
  37     }
  38 }
  39
  40 struct lru_zone*
  41 lru_new_zone(const char* name, evict_cb try_evict_cb)
  42 {
  43     struct lru_zone* zone = vzalloc(sizeof(struct lru_zone));
  44     if (!zone) {
  45         return NULL;
  46     }
  47
  48     zone->try_evict = try_evict_cb;
  49
  50     strncpy(zone->name, name, sizeof(zone->name) - 1);
  51     llist_init_head(&zone->lead_node);
  52     llist_append(&zone_lead, &zone->zones);
  53     spinlock_init(&zone->lock);
  54
  55     return zone;
  56 }
  57
  58 void
  59 lru_free_zone(struct lru_zone* zone)
  60 {
  61     lock(zone);
  62
  63     __lru_evict_all_lockness(zone);
  64
  65     if (llist_empty(&zone->lead_node)) {
  66         llist_delete(&zone->zones);
  67         vfree(zone);
  68         return;
  69     }
  70
  71     /*
  72         We are unable to free it at this moment,
  73         (probably due to tricky things happened
  74         to some cached object). Thus mark it and
  75         let the daemon try to free it asynchronously
  76     */
  77     zone->delayed_free = true;
  78     zone->attempts++;
  79
  80     unlock(zone);
  81 }
  82
  83 void
  84 lru_use_one(struct lru_zone* zone, struct lru_node* node)
  85 {
  86     lock(zone);
  87
  88     assert(!zone->delayed_free);
  89
  90     if (node->lru_nodes.next && node->lru_nodes.prev) {
  91         llist_delete(&node->lru_nodes);
  92     }
  93     else {
  94         zone->objects++;
  95     }
  96
  97     llist_prepend(&zone->lead_node, &node->lru_nodes);
  98     zone->hotness++;
  99
 100     unlock(zone);
 101 }
 102
 103 void
 104 lru_evict_one(struct lru_zone* zone)
 105 {
 106     lock(zone);
 107
 108     struct llist_header* tail = zone->lead_node.prev;
 109     if (tail == &zone->lead_node) {
 110         return;
 111     }
 112
 113     __do_evict_lockless(zone, tail);
 114
 115     unlock(zone);
 116 }
 117
 118 void
 119 lru_evict_half(struct lru_zone* zone)
 120 {
 121     lock(zone);
 122
 123     int target = (int)(zone->objects / 2);
 124     struct llist_header* tail = zone->lead_node.prev;
 125     while (tail != &zone->lead_node && target > 0) {
 126         __do_evict_lockless(zone, tail);
 127         tail = tail->prev;
 128         target--;
 129     }
 130
 131     zone->evict_stats.n_half++;
 132
 133     unlock(zone);
 134 }
 135
 136 void
 137 lru_evict_all(struct lru_zone* zone)
 138 {
 139     lock(zone);
 140
 141     __lru_evict_all_lockness(zone);
 142
 143     zone->evict_stats.n_full++;
 144
 145     unlock(zone);
 146 }
 147
 148 void
 149 lru_remove(struct lru_zone* zone, struct lru_node* node)
 150 {
 151     lock(zone);
 152
 153     if (node->lru_nodes.next && node->lru_nodes.prev) {
 154         llist_delete(&node->lru_nodes);
 155     }
 156     zone->objects--;
 157
 158     unlock(zone);
 159 }
 160
 161 static void
 162 read_lrulist_entry(struct twimap* map)
 163 {
 164     struct lru_zone* zone;
 165
 166     zone = twimap_index(map, struct lru_zone*);
 167     twimap_printf(map, "%s, %d, %d, %d, %d, %d, ",
 168                         zone->name,
 169                         zone->objects,
 170                         zone->hotness,
 171                         zone->evict_stats.n_single,
 172                         zone->evict_stats.n_half,
 173                         zone->evict_stats.n_full);
 174
 175     if (zone->delayed_free) {
 176         twimap_printf(map, "freeing %d attempts\n", zone->attempts);
 177     }
 178     else {
 179         twimap_printf(map, "active\n");
 180     }
 181 }
 182
 183 static void
 184 read_lrulist_reset(struct twimap* map)
 185 {
 186     map->index = container_of(&zone_lead, struct lru_zone, zones);
 187     twimap_printf(map, "name, n_objs, hot, n_evt, n_half, n_full, status\n");
 188 }
 189
 190 static int
 191 read_lrulist_next(struct twimap* map)
 192 {
 193     struct lru_zone* zone;
 194     struct llist_header* next;
 195
 196     zone = twimap_index(map, struct lru_zone*);
 197     next = zone->zones.next;
 198     if (next == &zone_lead) {
 199         return false;
 200     }
 201
 202     map->index = container_of(next, struct lru_zone, zones);
 203     return true;
 204 }
 205
 206 static void
 207 lru_pool_twimappable()
 208 {
 209     struct twimap* map;
 210
 211     map = twifs_mapping(NULL, NULL, "lru_pool");
 212     map->read = read_lrulist_entry;
 213     map->reset = read_lrulist_reset;
 214     map->go_next = read_lrulist_next;
 215 }
 216 EXPORT_TWIFS_PLUGIN(__lru_twimap, lru_pool_twimappable);