Loading...
1// SPDX-License-Identifier: GPL-2.0
2/*
3 * Lockless hierarchical page accounting & limiting
4 *
5 * Copyright (C) 2014 Red Hat, Inc., Johannes Weiner
6 */
7
8#include <linux/page_counter.h>
9#include <linux/atomic.h>
10#include <linux/kernel.h>
11#include <linux/string.h>
12#include <linux/sched.h>
13#include <linux/bug.h>
14#include <asm/page.h>
15
16static void propagate_protected_usage(struct page_counter *c,
17 unsigned long usage)
18{
19 unsigned long protected, old_protected;
20 long delta;
21
22 if (!c->parent)
23 return;
24
25 if (c->min || atomic_long_read(&c->min_usage)) {
26 if (usage <= c->min)
27 protected = usage;
28 else
29 protected = 0;
30
31 old_protected = atomic_long_xchg(&c->min_usage, protected);
32 delta = protected - old_protected;
33 if (delta)
34 atomic_long_add(delta, &c->parent->children_min_usage);
35 }
36
37 if (c->low || atomic_long_read(&c->low_usage)) {
38 if (usage <= c->low)
39 protected = usage;
40 else
41 protected = 0;
42
43 old_protected = atomic_long_xchg(&c->low_usage, protected);
44 delta = protected - old_protected;
45 if (delta)
46 atomic_long_add(delta, &c->parent->children_low_usage);
47 }
48}
49
50/**
51 * page_counter_cancel - take pages out of the local counter
52 * @counter: counter
53 * @nr_pages: number of pages to cancel
54 */
55void page_counter_cancel(struct page_counter *counter, unsigned long nr_pages)
56{
57 long new;
58
59 new = atomic_long_sub_return(nr_pages, &counter->usage);
60 propagate_protected_usage(counter, new);
61 /* More uncharges than charges? */
62 WARN_ON_ONCE(new < 0);
63}
64
65/**
66 * page_counter_charge - hierarchically charge pages
67 * @counter: counter
68 * @nr_pages: number of pages to charge
69 *
70 * NOTE: This does not consider any configured counter limits.
71 */
72void page_counter_charge(struct page_counter *counter, unsigned long nr_pages)
73{
74 struct page_counter *c;
75
76 for (c = counter; c; c = c->parent) {
77 long new;
78
79 new = atomic_long_add_return(nr_pages, &c->usage);
80 propagate_protected_usage(counter, new);
81 /*
82 * This is indeed racy, but we can live with some
83 * inaccuracy in the watermark.
84 */
85 if (new > c->watermark)
86 c->watermark = new;
87 }
88}
89
90/**
91 * page_counter_try_charge - try to hierarchically charge pages
92 * @counter: counter
93 * @nr_pages: number of pages to charge
94 * @fail: points first counter to hit its limit, if any
95 *
96 * Returns %true on success, or %false and @fail if the counter or one
97 * of its ancestors has hit its configured limit.
98 */
99bool page_counter_try_charge(struct page_counter *counter,
100 unsigned long nr_pages,
101 struct page_counter **fail)
102{
103 struct page_counter *c;
104
105 for (c = counter; c; c = c->parent) {
106 long new;
107 /*
108 * Charge speculatively to avoid an expensive CAS. If
109 * a bigger charge fails, it might falsely lock out a
110 * racing smaller charge and send it into reclaim
111 * early, but the error is limited to the difference
112 * between the two sizes, which is less than 2M/4M in
113 * case of a THP locking out a regular page charge.
114 *
115 * The atomic_long_add_return() implies a full memory
116 * barrier between incrementing the count and reading
117 * the limit. When racing with page_counter_limit(),
118 * we either see the new limit or the setter sees the
119 * counter has changed and retries.
120 */
121 new = atomic_long_add_return(nr_pages, &c->usage);
122 if (new > c->max) {
123 atomic_long_sub(nr_pages, &c->usage);
124 propagate_protected_usage(counter, new);
125 /*
126 * This is racy, but we can live with some
127 * inaccuracy in the failcnt.
128 */
129 c->failcnt++;
130 *fail = c;
131 goto failed;
132 }
133 propagate_protected_usage(counter, new);
134 /*
135 * Just like with failcnt, we can live with some
136 * inaccuracy in the watermark.
137 */
138 if (new > c->watermark)
139 c->watermark = new;
140 }
141 return true;
142
143failed:
144 for (c = counter; c != *fail; c = c->parent)
145 page_counter_cancel(c, nr_pages);
146
147 return false;
148}
149
150/**
151 * page_counter_uncharge - hierarchically uncharge pages
152 * @counter: counter
153 * @nr_pages: number of pages to uncharge
154 */
155void page_counter_uncharge(struct page_counter *counter, unsigned long nr_pages)
156{
157 struct page_counter *c;
158
159 for (c = counter; c; c = c->parent)
160 page_counter_cancel(c, nr_pages);
161}
162
163/**
164 * page_counter_set_max - set the maximum number of pages allowed
165 * @counter: counter
166 * @nr_pages: limit to set
167 *
168 * Returns 0 on success, -EBUSY if the current number of pages on the
169 * counter already exceeds the specified limit.
170 *
171 * The caller must serialize invocations on the same counter.
172 */
173int page_counter_set_max(struct page_counter *counter, unsigned long nr_pages)
174{
175 for (;;) {
176 unsigned long old;
177 long usage;
178
179 /*
180 * Update the limit while making sure that it's not
181 * below the concurrently-changing counter value.
182 *
183 * The xchg implies two full memory barriers before
184 * and after, so the read-swap-read is ordered and
185 * ensures coherency with page_counter_try_charge():
186 * that function modifies the count before checking
187 * the limit, so if it sees the old limit, we see the
188 * modified counter and retry.
189 */
190 usage = atomic_long_read(&counter->usage);
191
192 if (usage > nr_pages)
193 return -EBUSY;
194
195 old = xchg(&counter->max, nr_pages);
196
197 if (atomic_long_read(&counter->usage) <= usage)
198 return 0;
199
200 counter->max = old;
201 cond_resched();
202 }
203}
204
205/**
206 * page_counter_set_min - set the amount of protected memory
207 * @counter: counter
208 * @nr_pages: value to set
209 *
210 * The caller must serialize invocations on the same counter.
211 */
212void page_counter_set_min(struct page_counter *counter, unsigned long nr_pages)
213{
214 struct page_counter *c;
215
216 counter->min = nr_pages;
217
218 for (c = counter; c; c = c->parent)
219 propagate_protected_usage(c, atomic_long_read(&c->usage));
220}
221
222/**
223 * page_counter_set_low - set the amount of protected memory
224 * @counter: counter
225 * @nr_pages: value to set
226 *
227 * The caller must serialize invocations on the same counter.
228 */
229void page_counter_set_low(struct page_counter *counter, unsigned long nr_pages)
230{
231 struct page_counter *c;
232
233 counter->low = nr_pages;
234
235 for (c = counter; c; c = c->parent)
236 propagate_protected_usage(c, atomic_long_read(&c->usage));
237}
238
239/**
240 * page_counter_memparse - memparse() for page counter limits
241 * @buf: string to parse
242 * @max: string meaning maximum possible value
243 * @nr_pages: returns the result in number of pages
244 *
245 * Returns -EINVAL, or 0 and @nr_pages on success. @nr_pages will be
246 * limited to %PAGE_COUNTER_MAX.
247 */
248int page_counter_memparse(const char *buf, const char *max,
249 unsigned long *nr_pages)
250{
251 char *end;
252 u64 bytes;
253
254 if (!strcmp(buf, max)) {
255 *nr_pages = PAGE_COUNTER_MAX;
256 return 0;
257 }
258
259 bytes = memparse(buf, &end);
260 if (*end != '\0')
261 return -EINVAL;
262
263 *nr_pages = min(bytes / PAGE_SIZE, (u64)PAGE_COUNTER_MAX);
264
265 return 0;
266}
1// SPDX-License-Identifier: GPL-2.0
2/*
3 * Lockless hierarchical page accounting & limiting
4 *
5 * Copyright (C) 2014 Red Hat, Inc., Johannes Weiner
6 */
7
8#include <linux/page_counter.h>
9#include <linux/atomic.h>
10#include <linux/kernel.h>
11#include <linux/string.h>
12#include <linux/sched.h>
13#include <linux/bug.h>
14#include <asm/page.h>
15
16static bool track_protection(struct page_counter *c)
17{
18 return c->protection_support;
19}
20
21static void propagate_protected_usage(struct page_counter *c,
22 unsigned long usage)
23{
24 unsigned long protected, old_protected;
25 long delta;
26
27 if (!c->parent)
28 return;
29
30 protected = min(usage, READ_ONCE(c->min));
31 old_protected = atomic_long_read(&c->min_usage);
32 if (protected != old_protected) {
33 old_protected = atomic_long_xchg(&c->min_usage, protected);
34 delta = protected - old_protected;
35 if (delta)
36 atomic_long_add(delta, &c->parent->children_min_usage);
37 }
38
39 protected = min(usage, READ_ONCE(c->low));
40 old_protected = atomic_long_read(&c->low_usage);
41 if (protected != old_protected) {
42 old_protected = atomic_long_xchg(&c->low_usage, protected);
43 delta = protected - old_protected;
44 if (delta)
45 atomic_long_add(delta, &c->parent->children_low_usage);
46 }
47}
48
49/**
50 * page_counter_cancel - take pages out of the local counter
51 * @counter: counter
52 * @nr_pages: number of pages to cancel
53 */
54void page_counter_cancel(struct page_counter *counter, unsigned long nr_pages)
55{
56 long new;
57
58 new = atomic_long_sub_return(nr_pages, &counter->usage);
59 /* More uncharges than charges? */
60 if (WARN_ONCE(new < 0, "page_counter underflow: %ld nr_pages=%lu\n",
61 new, nr_pages)) {
62 new = 0;
63 atomic_long_set(&counter->usage, new);
64 }
65 if (track_protection(counter))
66 propagate_protected_usage(counter, new);
67}
68
69/**
70 * page_counter_charge - hierarchically charge pages
71 * @counter: counter
72 * @nr_pages: number of pages to charge
73 *
74 * NOTE: This does not consider any configured counter limits.
75 */
76void page_counter_charge(struct page_counter *counter, unsigned long nr_pages)
77{
78 struct page_counter *c;
79 bool protection = track_protection(counter);
80
81 for (c = counter; c; c = c->parent) {
82 long new;
83
84 new = atomic_long_add_return(nr_pages, &c->usage);
85 if (protection)
86 propagate_protected_usage(c, new);
87 /*
88 * This is indeed racy, but we can live with some
89 * inaccuracy in the watermark.
90 *
91 * Notably, we have two watermarks to allow for both a globally
92 * visible peak and one that can be reset at a smaller scope.
93 *
94 * Since we reset both watermarks when the global reset occurs,
95 * we can guarantee that watermark >= local_watermark, so we
96 * don't need to do both comparisons every time.
97 *
98 * On systems with branch predictors, the inner condition should
99 * be almost free.
100 */
101 if (new > READ_ONCE(c->local_watermark)) {
102 WRITE_ONCE(c->local_watermark, new);
103 if (new > READ_ONCE(c->watermark))
104 WRITE_ONCE(c->watermark, new);
105 }
106 }
107}
108
109/**
110 * page_counter_try_charge - try to hierarchically charge pages
111 * @counter: counter
112 * @nr_pages: number of pages to charge
113 * @fail: points first counter to hit its limit, if any
114 *
115 * Returns %true on success, or %false and @fail if the counter or one
116 * of its ancestors has hit its configured limit.
117 */
118bool page_counter_try_charge(struct page_counter *counter,
119 unsigned long nr_pages,
120 struct page_counter **fail)
121{
122 struct page_counter *c;
123 bool protection = track_protection(counter);
124
125 for (c = counter; c; c = c->parent) {
126 long new;
127 /*
128 * Charge speculatively to avoid an expensive CAS. If
129 * a bigger charge fails, it might falsely lock out a
130 * racing smaller charge and send it into reclaim
131 * early, but the error is limited to the difference
132 * between the two sizes, which is less than 2M/4M in
133 * case of a THP locking out a regular page charge.
134 *
135 * The atomic_long_add_return() implies a full memory
136 * barrier between incrementing the count and reading
137 * the limit. When racing with page_counter_set_max(),
138 * we either see the new limit or the setter sees the
139 * counter has changed and retries.
140 */
141 new = atomic_long_add_return(nr_pages, &c->usage);
142 if (new > c->max) {
143 atomic_long_sub(nr_pages, &c->usage);
144 /*
145 * This is racy, but we can live with some
146 * inaccuracy in the failcnt which is only used
147 * to report stats.
148 */
149 data_race(c->failcnt++);
150 *fail = c;
151 goto failed;
152 }
153 if (protection)
154 propagate_protected_usage(c, new);
155
156 /* see comment on page_counter_charge */
157 if (new > READ_ONCE(c->local_watermark)) {
158 WRITE_ONCE(c->local_watermark, new);
159 if (new > READ_ONCE(c->watermark))
160 WRITE_ONCE(c->watermark, new);
161 }
162 }
163 return true;
164
165failed:
166 for (c = counter; c != *fail; c = c->parent)
167 page_counter_cancel(c, nr_pages);
168
169 return false;
170}
171
172/**
173 * page_counter_uncharge - hierarchically uncharge pages
174 * @counter: counter
175 * @nr_pages: number of pages to uncharge
176 */
177void page_counter_uncharge(struct page_counter *counter, unsigned long nr_pages)
178{
179 struct page_counter *c;
180
181 for (c = counter; c; c = c->parent)
182 page_counter_cancel(c, nr_pages);
183}
184
185/**
186 * page_counter_set_max - set the maximum number of pages allowed
187 * @counter: counter
188 * @nr_pages: limit to set
189 *
190 * Returns 0 on success, -EBUSY if the current number of pages on the
191 * counter already exceeds the specified limit.
192 *
193 * The caller must serialize invocations on the same counter.
194 */
195int page_counter_set_max(struct page_counter *counter, unsigned long nr_pages)
196{
197 for (;;) {
198 unsigned long old;
199 long usage;
200
201 /*
202 * Update the limit while making sure that it's not
203 * below the concurrently-changing counter value.
204 *
205 * The xchg implies two full memory barriers before
206 * and after, so the read-swap-read is ordered and
207 * ensures coherency with page_counter_try_charge():
208 * that function modifies the count before checking
209 * the limit, so if it sees the old limit, we see the
210 * modified counter and retry.
211 */
212 usage = page_counter_read(counter);
213
214 if (usage > nr_pages)
215 return -EBUSY;
216
217 old = xchg(&counter->max, nr_pages);
218
219 if (page_counter_read(counter) <= usage || nr_pages >= old)
220 return 0;
221
222 counter->max = old;
223 cond_resched();
224 }
225}
226
227/**
228 * page_counter_set_min - set the amount of protected memory
229 * @counter: counter
230 * @nr_pages: value to set
231 *
232 * The caller must serialize invocations on the same counter.
233 */
234void page_counter_set_min(struct page_counter *counter, unsigned long nr_pages)
235{
236 struct page_counter *c;
237
238 WRITE_ONCE(counter->min, nr_pages);
239
240 for (c = counter; c; c = c->parent)
241 propagate_protected_usage(c, atomic_long_read(&c->usage));
242}
243
244/**
245 * page_counter_set_low - set the amount of protected memory
246 * @counter: counter
247 * @nr_pages: value to set
248 *
249 * The caller must serialize invocations on the same counter.
250 */
251void page_counter_set_low(struct page_counter *counter, unsigned long nr_pages)
252{
253 struct page_counter *c;
254
255 WRITE_ONCE(counter->low, nr_pages);
256
257 for (c = counter; c; c = c->parent)
258 propagate_protected_usage(c, atomic_long_read(&c->usage));
259}
260
261/**
262 * page_counter_memparse - memparse() for page counter limits
263 * @buf: string to parse
264 * @max: string meaning maximum possible value
265 * @nr_pages: returns the result in number of pages
266 *
267 * Returns -EINVAL, or 0 and @nr_pages on success. @nr_pages will be
268 * limited to %PAGE_COUNTER_MAX.
269 */
270int page_counter_memparse(const char *buf, const char *max,
271 unsigned long *nr_pages)
272{
273 char *end;
274 u64 bytes;
275
276 if (!strcmp(buf, max)) {
277 *nr_pages = PAGE_COUNTER_MAX;
278 return 0;
279 }
280
281 bytes = memparse(buf, &end);
282 if (*end != '\0')
283 return -EINVAL;
284
285 *nr_pages = min(bytes / PAGE_SIZE, (u64)PAGE_COUNTER_MAX);
286
287 return 0;
288}
289
290
291#ifdef CONFIG_MEMCG
292/*
293 * This function calculates an individual page counter's effective
294 * protection which is derived from its own memory.min/low, its
295 * parent's and siblings' settings, as well as the actual memory
296 * distribution in the tree.
297 *
298 * The following rules apply to the effective protection values:
299 *
300 * 1. At the first level of reclaim, effective protection is equal to
301 * the declared protection in memory.min and memory.low.
302 *
303 * 2. To enable safe delegation of the protection configuration, at
304 * subsequent levels the effective protection is capped to the
305 * parent's effective protection.
306 *
307 * 3. To make complex and dynamic subtrees easier to configure, the
308 * user is allowed to overcommit the declared protection at a given
309 * level. If that is the case, the parent's effective protection is
310 * distributed to the children in proportion to how much protection
311 * they have declared and how much of it they are utilizing.
312 *
313 * This makes distribution proportional, but also work-conserving:
314 * if one counter claims much more protection than it uses memory,
315 * the unused remainder is available to its siblings.
316 *
317 * 4. Conversely, when the declared protection is undercommitted at a
318 * given level, the distribution of the larger parental protection
319 * budget is NOT proportional. A counter's protection from a sibling
320 * is capped to its own memory.min/low setting.
321 *
322 * 5. However, to allow protecting recursive subtrees from each other
323 * without having to declare each individual counter's fixed share
324 * of the ancestor's claim to protection, any unutilized -
325 * "floating" - protection from up the tree is distributed in
326 * proportion to each counter's *usage*. This makes the protection
327 * neutral wrt sibling cgroups and lets them compete freely over
328 * the shared parental protection budget, but it protects the
329 * subtree as a whole from neighboring subtrees.
330 *
331 * Note that 4. and 5. are not in conflict: 4. is about protecting
332 * against immediate siblings whereas 5. is about protecting against
333 * neighboring subtrees.
334 */
335static unsigned long effective_protection(unsigned long usage,
336 unsigned long parent_usage,
337 unsigned long setting,
338 unsigned long parent_effective,
339 unsigned long siblings_protected,
340 bool recursive_protection)
341{
342 unsigned long protected;
343 unsigned long ep;
344
345 protected = min(usage, setting);
346 /*
347 * If all cgroups at this level combined claim and use more
348 * protection than what the parent affords them, distribute
349 * shares in proportion to utilization.
350 *
351 * We are using actual utilization rather than the statically
352 * claimed protection in order to be work-conserving: claimed
353 * but unused protection is available to siblings that would
354 * otherwise get a smaller chunk than what they claimed.
355 */
356 if (siblings_protected > parent_effective)
357 return protected * parent_effective / siblings_protected;
358
359 /*
360 * Ok, utilized protection of all children is within what the
361 * parent affords them, so we know whatever this child claims
362 * and utilizes is effectively protected.
363 *
364 * If there is unprotected usage beyond this value, reclaim
365 * will apply pressure in proportion to that amount.
366 *
367 * If there is unutilized protection, the cgroup will be fully
368 * shielded from reclaim, but we do return a smaller value for
369 * protection than what the group could enjoy in theory. This
370 * is okay. With the overcommit distribution above, effective
371 * protection is always dependent on how memory is actually
372 * consumed among the siblings anyway.
373 */
374 ep = protected;
375
376 /*
377 * If the children aren't claiming (all of) the protection
378 * afforded to them by the parent, distribute the remainder in
379 * proportion to the (unprotected) memory of each cgroup. That
380 * way, cgroups that aren't explicitly prioritized wrt each
381 * other compete freely over the allowance, but they are
382 * collectively protected from neighboring trees.
383 *
384 * We're using unprotected memory for the weight so that if
385 * some cgroups DO claim explicit protection, we don't protect
386 * the same bytes twice.
387 *
388 * Check both usage and parent_usage against the respective
389 * protected values. One should imply the other, but they
390 * aren't read atomically - make sure the division is sane.
391 */
392 if (!recursive_protection)
393 return ep;
394
395 if (parent_effective > siblings_protected &&
396 parent_usage > siblings_protected &&
397 usage > protected) {
398 unsigned long unclaimed;
399
400 unclaimed = parent_effective - siblings_protected;
401 unclaimed *= usage - protected;
402 unclaimed /= parent_usage - siblings_protected;
403
404 ep += unclaimed;
405 }
406
407 return ep;
408}
409
410
411/**
412 * page_counter_calculate_protection - check if memory consumption is in the normal range
413 * @root: the top ancestor of the sub-tree being checked
414 * @counter: the page_counter the counter to update
415 * @recursive_protection: Whether to use memory_recursiveprot behavior.
416 *
417 * Calculates elow/emin thresholds for given page_counter.
418 *
419 * WARNING: This function is not stateless! It can only be used as part
420 * of a top-down tree iteration, not for isolated queries.
421 */
422void page_counter_calculate_protection(struct page_counter *root,
423 struct page_counter *counter,
424 bool recursive_protection)
425{
426 unsigned long usage, parent_usage;
427 struct page_counter *parent = counter->parent;
428
429 /*
430 * Effective values of the reclaim targets are ignored so they
431 * can be stale. Have a look at mem_cgroup_protection for more
432 * details.
433 * TODO: calculation should be more robust so that we do not need
434 * that special casing.
435 */
436 if (root == counter)
437 return;
438
439 usage = page_counter_read(counter);
440 if (!usage)
441 return;
442
443 if (parent == root) {
444 counter->emin = READ_ONCE(counter->min);
445 counter->elow = READ_ONCE(counter->low);
446 return;
447 }
448
449 parent_usage = page_counter_read(parent);
450
451 WRITE_ONCE(counter->emin, effective_protection(usage, parent_usage,
452 READ_ONCE(counter->min),
453 READ_ONCE(parent->emin),
454 atomic_long_read(&parent->children_min_usage),
455 recursive_protection));
456
457 WRITE_ONCE(counter->elow, effective_protection(usage, parent_usage,
458 READ_ONCE(counter->low),
459 READ_ONCE(parent->elow),
460 atomic_long_read(&parent->children_low_usage),
461 recursive_protection));
462}
463#endif /* CONFIG_MEMCG */