"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 }