Linux Audio

Check our new training course

Loading...
v4.17
  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
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 16/**
 17 * page_counter_cancel - take pages out of the local counter
 18 * @counter: counter
 19 * @nr_pages: number of pages to cancel
 20 */
 21void page_counter_cancel(struct page_counter *counter, unsigned long nr_pages)
 22{
 23	long new;
 24
 25	new = atomic_long_sub_return(nr_pages, &counter->count);
 26	/* More uncharges than charges? */
 27	WARN_ON_ONCE(new < 0);
 
 
 
 
 
 
 28}
 29
 30/**
 31 * page_counter_charge - hierarchically charge pages
 32 * @counter: counter
 33 * @nr_pages: number of pages to charge
 34 *
 35 * NOTE: This does not consider any configured counter limits.
 36 */
 37void page_counter_charge(struct page_counter *counter, unsigned long nr_pages)
 38{
 39	struct page_counter *c;
 
 40
 41	for (c = counter; c; c = c->parent) {
 42		long new;
 43
 44		new = atomic_long_add_return(nr_pages, &c->count);
 
 
 45		/*
 46		 * This is indeed racy, but we can live with some
 47		 * inaccuracy in the watermark.
 
 
 
 
 
 
 
 
 
 
 48		 */
 49		if (new > c->watermark)
 50			c->watermark = new;
 
 
 
 51	}
 52}
 53
 54/**
 55 * page_counter_try_charge - try to hierarchically charge pages
 56 * @counter: counter
 57 * @nr_pages: number of pages to charge
 58 * @fail: points first counter to hit its limit, if any
 59 *
 60 * Returns %true on success, or %false and @fail if the counter or one
 61 * of its ancestors has hit its configured limit.
 62 */
 63bool page_counter_try_charge(struct page_counter *counter,
 64			     unsigned long nr_pages,
 65			     struct page_counter **fail)
 66{
 67	struct page_counter *c;
 
 68
 69	for (c = counter; c; c = c->parent) {
 70		long new;
 71		/*
 72		 * Charge speculatively to avoid an expensive CAS.  If
 73		 * a bigger charge fails, it might falsely lock out a
 74		 * racing smaller charge and send it into reclaim
 75		 * early, but the error is limited to the difference
 76		 * between the two sizes, which is less than 2M/4M in
 77		 * case of a THP locking out a regular page charge.
 78		 *
 79		 * The atomic_long_add_return() implies a full memory
 80		 * barrier between incrementing the count and reading
 81		 * the limit.  When racing with page_counter_limit(),
 82		 * we either see the new limit or the setter sees the
 83		 * counter has changed and retries.
 84		 */
 85		new = atomic_long_add_return(nr_pages, &c->count);
 86		if (new > c->limit) {
 87			atomic_long_sub(nr_pages, &c->count);
 88			/*
 89			 * This is racy, but we can live with some
 90			 * inaccuracy in the failcnt.
 
 91			 */
 92			c->failcnt++;
 93			*fail = c;
 94			goto failed;
 95		}
 96		/*
 97		 * Just like with failcnt, we can live with some
 98		 * inaccuracy in the watermark.
 99		 */
100		if (new > c->watermark)
101			c->watermark = new;
 
 
 
102	}
103	return true;
104
105failed:
106	for (c = counter; c != *fail; c = c->parent)
107		page_counter_cancel(c, nr_pages);
108
109	return false;
110}
111
112/**
113 * page_counter_uncharge - hierarchically uncharge pages
114 * @counter: counter
115 * @nr_pages: number of pages to uncharge
116 */
117void page_counter_uncharge(struct page_counter *counter, unsigned long nr_pages)
118{
119	struct page_counter *c;
120
121	for (c = counter; c; c = c->parent)
122		page_counter_cancel(c, nr_pages);
123}
124
125/**
126 * page_counter_limit - limit the number of pages allowed
127 * @counter: counter
128 * @limit: limit to set
129 *
130 * Returns 0 on success, -EBUSY if the current number of pages on the
131 * counter already exceeds the specified limit.
132 *
133 * The caller must serialize invocations on the same counter.
134 */
135int page_counter_limit(struct page_counter *counter, unsigned long limit)
136{
137	for (;;) {
138		unsigned long old;
139		long count;
140
141		/*
142		 * Update the limit while making sure that it's not
143		 * below the concurrently-changing counter value.
144		 *
145		 * The xchg implies two full memory barriers before
146		 * and after, so the read-swap-read is ordered and
147		 * ensures coherency with page_counter_try_charge():
148		 * that function modifies the count before checking
149		 * the limit, so if it sees the old limit, we see the
150		 * modified counter and retry.
151		 */
152		count = atomic_long_read(&counter->count);
153
154		if (count > limit)
155			return -EBUSY;
156
157		old = xchg(&counter->limit, limit);
158
159		if (atomic_long_read(&counter->count) <= count)
160			return 0;
161
162		counter->limit = old;
163		cond_resched();
164	}
165}
166
167/**
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
168 * page_counter_memparse - memparse() for page counter limits
169 * @buf: string to parse
170 * @max: string meaning maximum possible value
171 * @nr_pages: returns the result in number of pages
172 *
173 * Returns -EINVAL, or 0 and @nr_pages on success.  @nr_pages will be
174 * limited to %PAGE_COUNTER_MAX.
175 */
176int page_counter_memparse(const char *buf, const char *max,
177			  unsigned long *nr_pages)
178{
179	char *end;
180	u64 bytes;
181
182	if (!strcmp(buf, max)) {
183		*nr_pages = PAGE_COUNTER_MAX;
184		return 0;
185	}
186
187	bytes = memparse(buf, &end);
188	if (*end != '\0')
189		return -EINVAL;
190
191	*nr_pages = min(bytes / PAGE_SIZE, (u64)PAGE_COUNTER_MAX);
192
193	return 0;
194}
v6.13.7
  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 */