add a real slab automover algorithm

converts the python script to C, more or less.

1 files changed, 150 insertions, 0 deletions

diff --git a/slab_automove.c b/slab_automove.c
new file mode 100644
index 0000000..8a66370
--- /dev/null
+++ b/slab_automove.c
@@ -0,0 +1,150 @@
+/*  Copyright 2017 Facebook.
+ *
+ *  Use and distribution licensed under the BSD license.  See
+ *  the LICENSE file for full text.
+ */
+
+/* -*- Mode: C; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
+#include "memcached.h"
+#include "slab_automove.h"
+#include <stdlib.h>
+#include <string.h>
+
+#define MIN_PAGES_FOR_SOURCE 2
+#define MIN_PAGES_FOR_RECLAIM 2.5
+
+struct window_data {
+    uint64_t age;
+    uint64_t dirty;
+    uint64_t evicted;
+};
+
+typedef struct {
+    struct window_data *window_data;
+    uint32_t window_size;
+    uint32_t window_cur;
+    double max_age_ratio;
+    item_stats_automove iam_before[MAX_NUMBER_OF_SLAB_CLASSES];
+    item_stats_automove iam_after[MAX_NUMBER_OF_SLAB_CLASSES];
+    slab_stats_automove sam_before[MAX_NUMBER_OF_SLAB_CLASSES];
+    slab_stats_automove sam_after[MAX_NUMBER_OF_SLAB_CLASSES];
+} slab_automove;
+
+void *slab_automove_init(uint32_t window_size, double max_age_ratio) {
+    slab_automove *a = calloc(1, sizeof(slab_automove));
+    if (a == NULL)
+        return NULL;
+    a->window_data = calloc(window_size * MAX_NUMBER_OF_SLAB_CLASSES, sizeof(struct window_data));
+    a->window_size = window_size;
+    a->max_age_ratio = max_age_ratio;
+    if (a->window_data == NULL) {
+        free(a);
+        return NULL;
+    }
+
+    // do a dry run to fill the before structs
+    fill_item_stats_automove(a->iam_before);
+    fill_slab_stats_automove(a->sam_before);
+
+    return (void *)a;
+}
+
+void slab_automove_free(void *arg) {
+    slab_automove *a = (slab_automove *)arg;
+    free(a->window_data);
+    free(a);
+}
+
+static void window_sum(struct window_data *wd, struct window_data *w, uint32_t size) {
+    int x;
+    for (x = 0; x < size; x++) {
+        struct window_data *d = &wd[x];
+        w->age += d->age;
+        w->dirty += d->dirty;
+        w->evicted += d->evicted;
+    }
+}
+
+// TODO: if oldest is dirty, find next oldest.
+// still need to base ratio off of absolute age
+void slab_automove_run(void *arg, int *src, int *dst) {
+    slab_automove *a = (slab_automove *)arg;
+    int n;
+    struct window_data w_sum;
+    int oldest = -1;
+    uint64_t oldest_age = 0;
+    int youngest = -1;
+    uint64_t youngest_age = ~0;
+    bool youngest_evicting = false;
+    *src = -1;
+    *dst = -1;
+
+    // fill after structs
+    fill_item_stats_automove(a->iam_after);
+    fill_slab_stats_automove(a->sam_after);
+    a->window_cur++;
+
+    // iterate slabs
+    for (n = POWER_SMALLEST; n < MAX_NUMBER_OF_SLAB_CLASSES; n++) {
+        int w_offset = n * a->window_size;
+        struct window_data *wd = &a->window_data[w_offset + (a->window_cur % a->window_size)];
+        memset(wd, 0, sizeof(struct window_data));
+        // summarize the window-up-to-now.
+        memset(&w_sum, 0, sizeof(struct window_data));
+        window_sum(&a->window_data[w_offset], &w_sum, a->window_size);
+
+        // if page delta, or evicted delta, mark window dirty
+        // (or outofmemory)
+        if (a->iam_after[n].evicted - a->iam_before[n].evicted > 0 ||
+            a->iam_after[n].outofmemory - a->iam_before[n].outofmemory > 0) {
+            wd->evicted = 1;
+            wd->dirty = 1;
+        }
+        if (a->sam_after[n].total_pages - a->sam_before[n].total_pages > 0) {
+            wd->dirty = 1;
+        }
+
+        // set age into window
+        wd->age = a->iam_after[n].age;
+
+        // grab age as average of window total
+        uint64_t age = w_sum.age / a->window_size;
+
+        // if > N free chunks and not dirty, make decision.
+        if (a->sam_after[n].free_chunks > a->sam_after[n].chunks_per_page * MIN_PAGES_FOR_RECLAIM) {
+            if (w_sum.dirty == 0) {
+                *src = n;
+                *dst = 0;
+                break;
+            }
+        }
+
+        // if oldest and have enough pages, is oldest
+        if (age > oldest_age && a->sam_after[n].total_pages > MIN_PAGES_FOR_SOURCE) {
+            oldest = n;
+            oldest_age = age;
+        }
+
+        // grab evicted count from window
+        // if > half the window and youngest, mark as youngest
+        if (age < youngest_age && w_sum.evicted > a->window_size / 2) {
+            youngest = n;
+            youngest_age = age;
+            youngest_evicting = wd->evicted ? true : false;
+        }
+    }
+
+    memcpy(a->iam_before, a->iam_after,
+            sizeof(item_stats_automove) * MAX_NUMBER_OF_SLAB_CLASSES);
+    memcpy(a->sam_before, a->sam_after,
+            sizeof(slab_stats_automove) * MAX_NUMBER_OF_SLAB_CLASSES);
+    // if we have a youngest and oldest, and oldest is outside the ratio,
+    // also, only make decisions if window has filled once.
+    if (youngest != -1 && oldest != -1 && a->window_cur > a->window_size) {
+        if (youngest_age < ((double)oldest_age * a->max_age_ratio) && youngest_evicting) {
+            *src = oldest;
+            *dst = youngest;
+        }
+    }
+    return;
+}