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 #include <lunaix/kthread.h>
   7 #include <lunaix/owloysius.h>
   8
   9 #include <klibc/string.h>
  10
  11 static struct llist_header zone_lead = { .next = &zone_lead, .prev = &zone_lead };
  12
  13 DEFINE_SPINLOCK_OPS(struct lru_zone*, lock);
  14 static DEFINE_SPINLOCK(zone_list_lock);
  15
  16 static void
  17 __do_evict_nolock(struct lru_zone* zone, struct llist_header* elem)
  18 {
  19     llist_delete(elem);
  20     if (!zone->try_evict(container_of(elem, struct lru_node, lru_nodes))) {
  21         // if the node is unable to evict, raise it's rank by one, so
  22         // others can have chance in the next round
  23         struct llist_header* new_tail = zone->lead_node.prev;
  24         llist_prepend(new_tail, elem);
  25     } else {
  26         zone->objects--;
  27     }
  28
  29     zone->evict_stats.n_single++;
  30 }
  31
  32 static void
  33 __lru_evict_all_nolock(struct lru_zone* zone)
  34 {
  35     struct llist_header* tail, *curr;
  36
  37     tail = zone->lead_node.prev;
  38     while (tail != &zone->lead_node)
  39     {
  40         curr = tail;
  41         tail = tail->prev;
  42         __do_evict_nolock(zone, curr);
  43     }
  44 }
  45
  46 struct lru_zone*
  47 lru_new_zone(const char* name, evict_cb try_evict_cb)
  48 {
  49     struct lru_zone* zone = vzalloc(sizeof(struct lru_zone));
  50     if (!zone) {
  51         return NULL;
  52     }
  53
  54     zone->try_evict = try_evict_cb;
  55
  56     strncpy(zone->name, name, sizeof(zone->name) - 1);
  57     llist_init_head(&zone->lead_node);
  58     spinlock_init(&zone->lock);
  59
  60     spinlock_acquire(&zone_list_lock);
  61     llist_append(&zone_lead, &zone->zones);
  62     spinlock_release(&zone_list_lock);
  63
  64     return zone;
  65 }
  66
  67 void
  68 lru_free_zone(struct lru_zone* zone)
  69 {
  70     lock(zone);
  71
  72     __lru_evict_all_nolock(zone);
  73
  74     if (llist_empty(&zone->lead_node))
  75     {
  76         llist_delete(&zone->zones);
  77         unlock(zone);
  78         vfree(zone);
  79         return;
  80     }
  81
  82     /*
  83         We are unable to free it at this moment,
  84         (probably due to tricky things happened
  85         to some cached object). Thus mark it and
  86         let the daemon try to free it asynchronously
  87     */
  88     zone->delayed_free = true;
  89     zone->attempts++;
  90
  91     unlock(zone);
  92 }
  93
  94 void
  95 lru_use_one(struct lru_zone* zone, struct lru_node* node)
  96 {
  97     lock(zone);
  98
  99     assert(!zone->delayed_free);
 100
 101     if (node->lru_nodes.next && node->lru_nodes.prev) {
 102         llist_delete(&node->lru_nodes);
 103     }
 104     else {
 105         zone->objects++;
 106     }
 107
 108     llist_prepend(&zone->lead_node, &node->lru_nodes);
 109     zone->hotness++;
 110
 111     unlock(zone);
 112 }
 113
 114 void
 115 lru_evict_one(struct lru_zone* zone)
 116 {
 117     lock(zone);
 118
 119     struct llist_header* tail = zone->lead_node.prev;
 120     if (tail == &zone->lead_node) {
 121         goto done;
 122     }
 123
 124     __do_evict_nolock(zone, tail);
 125
 126 done:
 127     unlock(zone);
 128 }
 129
 130 void
 131 lru_evict_half(struct lru_zone* zone)
 132 {
 133     int target;
 134     struct llist_header *tail, *curr;
 135
 136     lock(zone);
 137
 138     target = (int)(zone->objects / 2);
 139     tail = zone->lead_node.prev;
 140
 141     while (tail != &zone->lead_node && target > 0) {
 142         curr = tail;
 143         tail = tail->prev;
 144
 145         __do_evict_nolock(zone, curr);
 146         target--;
 147     }
 148
 149     zone->evict_stats.n_half++;
 150
 151     unlock(zone);
 152 }
 153
 154 void
 155 lru_evict_all(struct lru_zone* zone)
 156 {
 157     lock(zone);
 158
 159     __lru_evict_all_nolock(zone);
 160
 161     zone->evict_stats.n_full++;
 162
 163     unlock(zone);
 164 }
 165
 166 void
 167 lru_remove(struct lru_zone* zone, struct lru_node* node)
 168 {
 169     if (llist_empty(&node->lru_nodes))
 170         return;
 171
 172     lock(zone);
 173
 174     llist_delete(&node->lru_nodes);
 175     zone->objects--;
 176
 177     unlock(zone);
 178 }
 179
 180
 181 static void
 182 __lru_pool_daemon()
 183 {
 184     struct lru_zone *pos, *n;
 185
 186     while (true)
 187     {
 188         spinlock_acquire(&zone_list_lock);
 189
 190         // TODO add a watermark check before doing eviction
 191         llist_for_each(pos, n, &zone_lead, zones) {
 192             lru_evict_half(pos);
 193         }
 194
 195         spinlock_release(&zone_list_lock);
 196
 197         kthread_sleep(10);
 198     }
 199 }
 200
 201 static void
 202 __lru_pool_init()
 203 {
 204     // TODO make sure other are thread-safe first
 205
 206     // kthread_spawn((ptr_t)__lru_pool_daemon);
 207 }
 208 owloysius_fetch_init(__lru_pool_init, on_postboot)
 209
 210
 211 static void
 212 __twimap_read_lru_pool(struct twimap* map)
 213 {
 214     struct lru_zone* zone;
 215
 216     zone = twimap_index(map, struct lru_zone*);
 217     twimap_printf(map, "%s, %d, %d, %d, %d, %d, ",
 218                         zone->name,
 219                         zone->objects,
 220                         zone->hotness,
 221                         zone->evict_stats.n_single,
 222                         zone->evict_stats.n_half,
 223                         zone->evict_stats.n_full);
 224
 225     if (zone->delayed_free) {
 226         twimap_printf(map, "freeing %d attempts\n", zone->attempts);
 227     }
 228     else {
 229         twimap_printf(map, "active\n");
 230     }
 231 }
 232
 233 static void
 234 __twimap_reset_lru_pool(struct twimap* map)
 235 {
 236     map->index = container_of(&zone_lead, struct lru_zone, zones);
 237     twimap_printf(map, "name, n_objs, hot, n_evt, n_half, n_full, status\n");
 238 }
 239
 240 static int
 241 __twimap_gonext_lru_pool(struct twimap* map)
 242 {
 243     struct lru_zone* zone;
 244     struct llist_header* next;
 245
 246     zone = twimap_index(map, struct lru_zone*);
 247     next = zone->zones.next;
 248     if (next == &zone_lead) {
 249         return false;
 250     }
 251
 252     map->index = container_of(next, struct lru_zone, zones);
 253     return true;
 254 }
 255
 256 static void
 257 lru_pool_twimappable()
 258 {
 259     twimap_export_list(NULL, lru_pool, FSACL_aR, NULL);
 260 }
 261 EXPORT_TWIFS_PLUGIN(__lru_twimap, lru_pool_twimappable);