"Fossies" - the Fresh Open Source Software Archive

Member "memcached-1.6.15/slab_automove.c" (21 Feb 2022, 5686 Bytes) of package /linux/www/memcached-1.6.15.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "slab_automove.c" see the Fossies "Dox" file reference documentation.

    1 /*  Copyright 2017 Facebook.
    2  *
    3  *  Use and distribution licensed under the BSD license.  See
    4  *  the LICENSE file for full text.
    5  */
    6 
    7 /* -*- Mode: C; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
    8 #include "memcached.h"
    9 #include "slab_automove.h"
   10 #include <stdlib.h>
   11 #include <string.h>
   12 
   13 #define MIN_PAGES_FOR_SOURCE 2
   14 #define MIN_PAGES_FOR_RECLAIM 2.5
   15 
   16 struct window_data {
   17     uint64_t age;
   18     uint64_t dirty;
   19     float evicted_ratio;
   20     uint64_t evicted_seen; // if evictions were seen at all this window
   21 };
   22 
   23 typedef struct {
   24     struct window_data *window_data;
   25     uint32_t window_size;
   26     uint32_t window_cur;
   27     double max_age_ratio;
   28     item_stats_automove iam_before[MAX_NUMBER_OF_SLAB_CLASSES];
   29     item_stats_automove iam_after[MAX_NUMBER_OF_SLAB_CLASSES];
   30     slab_stats_automove sam_before[MAX_NUMBER_OF_SLAB_CLASSES];
   31     slab_stats_automove sam_after[MAX_NUMBER_OF_SLAB_CLASSES];
   32 } slab_automove;
   33 
   34 void *slab_automove_init(struct settings *settings) {
   35     uint32_t window_size = settings->slab_automove_window;
   36     double max_age_ratio = settings->slab_automove_ratio;
   37     slab_automove *a = calloc(1, sizeof(slab_automove));
   38     if (a == NULL)
   39         return NULL;
   40     a->window_data = calloc(window_size * MAX_NUMBER_OF_SLAB_CLASSES, sizeof(struct window_data));
   41     a->window_size = window_size;
   42     a->max_age_ratio = max_age_ratio;
   43     if (a->window_data == NULL) {
   44         free(a);
   45         return NULL;
   46     }
   47 
   48     // do a dry run to fill the before structs
   49     fill_item_stats_automove(a->iam_before);
   50     fill_slab_stats_automove(a->sam_before);
   51 
   52     return (void *)a;
   53 }
   54 
   55 void slab_automove_free(void *arg) {
   56     slab_automove *a = (slab_automove *)arg;
   57     free(a->window_data);
   58     free(a);
   59 }
   60 
   61 static void window_sum(struct window_data *wd, struct window_data *w, uint32_t size) {
   62     int x;
   63     for (x = 0; x < size; x++) {
   64         struct window_data *d = &wd[x];
   65         w->age += d->age;
   66         w->dirty += d->dirty;
   67         w->evicted_ratio += d->evicted_ratio;
   68         w->evicted_seen += d->evicted_seen;
   69     }
   70 }
   71 
   72 // TODO: if oldest is dirty, find next oldest.
   73 // still need to base ratio off of absolute age
   74 void slab_automove_run(void *arg, int *src, int *dst) {
   75     slab_automove *a = (slab_automove *)arg;
   76     int n;
   77     struct window_data w_sum;
   78     int oldest = -1;
   79     uint64_t oldest_age = 0;
   80     int youngest = -1;
   81     uint64_t youngest_age = ~0;
   82     bool youngest_evicting = false;
   83     *src = -1;
   84     *dst = -1;
   85 
   86     // fill after structs
   87     fill_item_stats_automove(a->iam_after);
   88     fill_slab_stats_automove(a->sam_after);
   89     // Loop once to get total_evicted for this window.
   90     uint64_t evicted_total = 0;
   91     for (n = POWER_SMALLEST; n < MAX_NUMBER_OF_SLAB_CLASSES; n++) {
   92         evicted_total += a->iam_after[n].evicted - a->iam_before[n].evicted;
   93     }
   94     a->window_cur++;
   95 
   96     // iterate slabs
   97     for (n = POWER_SMALLEST; n < MAX_NUMBER_OF_SLAB_CLASSES; n++) {
   98         int w_offset = n * a->window_size;
   99         struct window_data *wd = &a->window_data[w_offset + (a->window_cur % a->window_size)];
  100         memset(wd, 0, sizeof(struct window_data));
  101         // summarize the window-up-to-now.
  102         memset(&w_sum, 0, sizeof(struct window_data));
  103         window_sum(&a->window_data[w_offset], &w_sum, a->window_size);
  104 
  105         // if page delta, or evicted delta, mark window dirty
  106         // (or outofmemory)
  107         uint64_t evicted_delta = a->iam_after[n].evicted - a->iam_before[n].evicted;
  108         if (evicted_delta > 0) {
  109             // FIXME: the python script is using floats. we have ints.
  110             wd->evicted_ratio = (float) evicted_delta / evicted_total;
  111             wd->evicted_seen = 1;
  112             wd->dirty = 1;
  113         }
  114 
  115         if (a->iam_after[n].outofmemory - a->iam_before[n].outofmemory > 0) {
  116             wd->dirty = 1;
  117         }
  118         if (a->sam_after[n].total_pages - a->sam_before[n].total_pages > 0) {
  119             wd->dirty = 1;
  120         }
  121 
  122         // set age into window
  123         wd->age = a->iam_after[n].age;
  124 
  125         // grab age as average of window total
  126         uint64_t age = w_sum.age / a->window_size;
  127 
  128         // if > N free chunks and not dirty, make decision.
  129         if (a->sam_after[n].free_chunks > a->sam_after[n].chunks_per_page * MIN_PAGES_FOR_RECLAIM) {
  130             if (w_sum.dirty == 0) {
  131                 *src = n;
  132                 *dst = 0;
  133                 break;
  134             }
  135         }
  136 
  137         // if oldest and have enough pages, is oldest
  138         if (age > oldest_age && a->sam_after[n].total_pages > MIN_PAGES_FOR_SOURCE) {
  139             oldest = n;
  140             oldest_age = age;
  141         }
  142 
  143         // grab evicted count from window
  144         // if > half the window and youngest, mark as youngest
  145         // or, if more than 25% of total evictions in the window.
  146         if (age < youngest_age && (w_sum.evicted_seen > a->window_size / 2
  147                     || w_sum.evicted_ratio / a->window_size > 0.25)) {
  148             youngest = n;
  149             youngest_age = age;
  150             youngest_evicting = wd->evicted_seen ? true : false;
  151         }
  152     }
  153 
  154     memcpy(a->iam_before, a->iam_after,
  155             sizeof(item_stats_automove) * MAX_NUMBER_OF_SLAB_CLASSES);
  156     memcpy(a->sam_before, a->sam_after,
  157             sizeof(slab_stats_automove) * MAX_NUMBER_OF_SLAB_CLASSES);
  158     // if we have a youngest and oldest, and oldest is outside the ratio,
  159     // also, only make decisions if window has filled once.
  160     if (youngest != -1 && oldest != -1 && a->window_cur > a->window_size) {
  161         if (youngest_age < ((double)oldest_age * a->max_age_ratio) && youngest_evicting) {
  162             *src = oldest;
  163             *dst = youngest;
  164         }
  165     }
  166     return;
  167 }