mm/vmalloc: Cache the /proc/meminfo vmalloc statistics

I'd think you could easily fix that with a seqlock-like system.

What makes it so simple is that you can always fall back to calc_vmalloc_info if there's any problem, rather than looping or blocking.

The basic idea is that you have a seqlock counter, but if either of the two lsbits are set, the cached information is stale.

Basically, you need a seqlock and a spinlock. The seqlock does most of the work, and the spinlock ensures that there's only one updater of the cache.

vmap_unlock() does set_bit(0, &seq->sequence). This marks the information as stale.

get_vmalloc_info reads the seqlock. There are two case:
- If the two lsbits are 10, the cached information is valid.
Copy it out, re-check the seqlock, and loop if the sequence number changes.
- In any other case, the cached information is
not valid.
- Try to obtain the spinlock. Do not block if it's unavailable.
- If unavailable, do not block.
- If the lock is acquired:
- Set the sequence to (sequence | 3) + 1 (we're the only writer)
- This bumps the sequence number and leaves the lsbits at 00 (invalid)
- Memory barrier TBD. Do the RCU ops in calc_vmalloc_info do it for us?
- Call calc_vmalloc_info
- If we obtained the spinlock earlier:
- Copy our vmi to cached_info
- smp_wmb()
- set_bit(1, &seq->sequence). This marks the information as valid, as long as bit 0 is still clear.
- Release the spinlock.

Basically, bit 0 says "vmalloc info has changed", and bit 1 says "vmalloc cache has been updated". This clears bit 0 before starting the update so that an update during calc_vmalloc_info will force a new update.

So the three case are basically:
00 - calc_vmalloc_info() in progress
01 - vmap_unlock() during calc_vmalloc_info()
10 - cached_info is valid
11 - vmap_unlock has invalidated cached_info, awaiting refresh

Logically, the sequence number should be initialized to ...01, but the code above handles 00 okay.

I think this is too complex.

How about something simple like the patch below (on top of the third patch)?

It makes the vmalloc info transactional - /proc/meminfo will always print a consistent set of numbers. (Not that we really care about races there, but it looks really simple to solve so why not.)

( I also moved the function-static cache next to the flag and seqlock - this
should further compress the cache footprint. )

Have I missed anything? Very lightly tested: booted in a VM.

Thanks,

Ingo

=========================>

 mm/vmalloc.c | 23 ++++++++++++++++++-----
 1 file changed, 18 insertions(+), 5 deletions(-)

index ef48e557df5a..66726f41e726 100644
@@ -278,7 +278,15 @@ EXPORT_SYMBOL(vmalloc_to_pfn);
 
 static __cacheline_aligned_in_smp DEFINE_SPINLOCK(vmap_area_lock);
 
+/*
+ * Seqlock and flag for the vmalloc info cache printed in /proc/meminfo.
+ *
+ * The assumption of the optimization is that it's read frequently, but
+ * modified infrequently.
+ */
+static DEFINE_SEQLOCK(vmap_info_lock);
 static int vmap_info_changed;
+static struct vmalloc_info vmap_info_cache;
 
 static inline void vmap_lock(void)
 {

@@ -2752,10 +2760,14 @@ static void calc_vmalloc_info(struct vmalloc_info *vmi)
 
 void get_vmalloc_info(struct vmalloc_info *vmi)
 {
-	static struct vmalloc_info cached_info;
+	if (!READ_ONCE(vmap_info_changed)) {
+		unsigned int seq;
+
+		do {
+			seq = read_seqbegin(&vmap_info_lock);
+			*vmi = vmap_info_cache;
+		} while (read_seqretry(&vmap_info_lock, seq));
 
-	if (!vmap_info_changed) {
-		*vmi = cached_info;
 		return;
 	}
 

@@ -2764,8 +2776,9 @@ void get_vmalloc_info(struct vmalloc_info *vmi)
 
 	calc_vmalloc_info(vmi);
 
-	barrier();
-	cached_info = *vmi;
+	write_seqlock(&vmap_info_lock);
+	vmap_info_cache = *vmi;
+	write_sequnlock(&vmap_info_lock);
 }
 
 #endif

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Looks like a huge simplification!

It needs a comment about the approximate nature of the locking and the obvious race conditions:
1) The first caller to get_vmalloc_info() clears vmap_info_changed before updating vmap_info_cache, so a second caller is likely to get stale data for the duration of a calc_vmalloc_info call.
2) Although unlikely, it's possible for two threads to race calling calc_vmalloc_info, and the one that computes fresher data updates the cache first, so the later write leaves stale data.

Other issues:
3) Me, I'd make vmap_info_changed a bool, for documentation more than any space saving.
4) I wish there were a trylock version of write_seqlock, so we could avoid blocking entirely. (You *could* hand-roll it, but that eats into the simplicity.)

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Ok, fair enough - so how about the attached approach instead, which uses a 64-bit generation counter to track changes to the vmalloc state.

This is still very simple, but should not suffer from stale data being returned indefinitely in /proc/meminfo. We might race - but that was true before as well due to the lock-less RCU list walk - but we'll always return a correct and consistent version of the information.

Lightly tested. This is a replacement patch to make it easier to read via email.

I also made sure there's no extra overhead in the !CONFIG_PROC_FS case.

Note that there's an even simpler variant possible I think: we could use just the two generation counters and barriers to remove the seqlock.

Thanks,

Ingo

==============================>

How does this invalidation approach compare to the jiffies approach? In other words, how often does the vmalloc info actually change (or rather, in this approximation, how often is vmap_area_lock taken)? In particular, does it also solve the problem with git's test suite and similar situations with lots of short-lived processes?

Not quite: It is done by the two functions get_{av,}phys_pages functions; and get_phys_pages is called (once per process) by glibc's qsort implementation. In fact, sysinfo() is (at least part of) the cure, not the disease. Whether qsort should care about the total amount of memory is another discussion.

<http://thread.gmane.org/gmane.comp.lib.glibc.alpha/54342/focus=54558>

Rasmus

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

The two approaches are pretty similar, and in a typical distro with typical workload vmalloc() is mostly a boot time affair.

But vmalloc() can be used more often in certain corner cases - neither of the patches makes that in any way slower, just the optimization won't trigger that often.

Since vmalloc() use is suboptimal for several reasons (it does not use large pages for kernel space allocations, etc.), this is all pretty OK IMHO.

Thanks, is the fixed up changelog below better?

Ingo

===============>

mm/vmalloc: Cache the vmalloc memory info

Linus reported that for scripting-intense workloads such as the Git build, glibc's qsort will read /proc/meminfo for every process created (by way of get_phys_pages()), which causes the Git build to generate a surprising amount of kernel overhead.

A fair chunk of the overhead is due to get_vmalloc_info() - which walks a potentially long list to do its statistics.

Modify Linus's jiffies based patch to use generation counters to cache the vmalloc info: vmap_unlock() increases the generation counter, and the get_vmalloc_info() reads it and compares it against a cached generation counter.

Also use a seqlock to make sure we always print a consistent set of vmalloc statistics.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Yes, though Linus specifically referred to "make test" (but I guess one could/should consider that part of the build process).

Rasmus

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

I was curious why these fields were ever added to /proc/meminfo, and dug up this:

commit d262ee3ee6ba4f5f6125571d93d9d63191d2ef76

Author: Andrew Morton <[email protected]>
Date:   Sat Apr 12 12:59:04 2003 -0700

[PATCH] vmalloc stats in /proc/meminfo

From: Matt Porter <[email protected]>

There was a thread a while back on lkml where Dave Hansen proposed this simple vmalloc usage reporting patch. The thread pretty much died out as most people seemed focused on what VM loading type bugs it could solve. I had posted that this type of information was really valuable in debugging embedded Linux board ports. A common example is where people do arch specific setup that limits there vmalloc space and then they find modules won't load. ;) Having the Vmalloc* info readily available is real useful in helping folks to fix their kernel ports.

That thread is at <http://thread.gmane.org/gmane.linux.kernel/53360>.

[Maybe one could just remove the fields and see if anybody actually notices/cares any longer. Or, if they are only used by kernel developers, put them in their own file.]

Rasmus

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

So instead of removing the fields (which I'm quite sure is an ABI breaker as it could break less robust /proc/meminfo parsers and scripts), we could just report '0' all the time - and have the real info somewhere else?

Thanks,

Ingo

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

I'm actually inclined to try exactly that for 4.3, and then take Ingo's patch as a fallback in case somebody actually notices.

I'm not convinced anybody actually uses those values, and they are getting *less* relevant rather than more (on 64-bit, those values really don't matter, since the vmalloc space isn't really a limitation), so let's try removing them and seeing what happens. And then we know what we can do if somebody does actually notice.

Linus

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Side note: the people who actually care about "my vmalloc area is too full, what's up?" would use /proc/vmallocinfo anyway, since that's what shows things like fragmentation etc.

So I'm just talking about removing the /proc/meminfo part. First try to remove it *all*, and if there is some script that hollers because it wants to parse them, print out the values as zero.

Linus

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

First, an actual, albeit minor, bug: initializing both vmap_info_gen and vmap_info_cache_gen to 0 marks the cache as valid, which it's not.

vmap_info_gen should be initialized to 1 to force an initial cache update.

Second, I don't see why you need a 64-bit counter. Seqlocks consider 32 bits (31 bits, actually, the lsbit means "update in progress") quite a strong enough guarantee.

Third, it seems as though vmap_info_cache_gen is basically a duplicate of vmap_info_lock.sequence. It should be possible to make one variable serve both purposes.

You just need a kludge to handle the case of multiple vamp_info updates between cache updates.

There are two simple ones:

1) Avoid bumping vmap_info_gen unnecessarily. In vmap_unlock(), do

	vmap_info_gen = (vmap_info_lock.sequence | 1) + 1;

2) - Make vmap_info_gen a seqcount_t
- In vmap_unlock(), do write_seqcount_barrier(&vmap_info_gen)
- In get_vmalloc_info, inside the seqlock critical section, do vmap_info_lock.seqcount.sequence = vmap_info_gen.sequence - 1; (Using the vmap_info_gen.sequence read while validating the cache in the first place.)

I should try to write an actual patch illustrating this.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Ha! :-) Fixed.

Yeah.

Just out of general paranoia - but you are right, and this would lower the overhead on 32-bit SMP platforms a bit, plus it avoids 64-bit word tearing artifacts on 32 bit platforms as well.

I modified it to u32.

Correct, I alluded to that in my description:

So I think something like the patch below is even simpler than trying to kludge generation counter semantics into seqcounts.

I used two generation counters and a spinlock. The fast path is completely lockless and lightweight on modern SMP platforms. (where smp_rmb() is a no-op or very cheap.)

There's not even a seqlock retry loop, instead an invalid cache causes us to fall back to the old behavior - and the freshest result is guaranteed to end up in the cache.

The linecount got a bit larger: but half of it is comments.

Note that the generation counters are signed integers so that this comparison can be done:

+ if (gen-vmap_info_cache_gen > 0) {

Thanks,

Ingo

======================>

I.e. something like the updated patch below. (We still need the WRITE_ONCE() for vmap_info_gen update.)

Thanks,

Ingo

========================>

(I hope I'm not annoying you by bikeshedding this too much, although I think this is improving.)

You've sort of re-invented spinlocks, but after thinking a bit, it all works.

Rather than using a single word, which is incremented to an odd number at the start of an update and an even number at the end, there are two. An update is in progress when they're unequal.

vmap_info_gen is incremented early, when the cache needs updating, and read late (after the cache is copied).

vmap_info_cache_gen is incremented after the cache is updated, and read early (before the cache is copied).

This is logically equivalent to my complicated scheme with atomic updates to various bits in a single generation word, but greatly simplified by having two separate words. In particular, there's no longer a need to distinguish "vmap has updated list" from "calc_vmalloc_info in progress".

I particularly like the "gen - vmap_info_cache_gen > 0" test. You *must* test for inequality to prevent tearing of a valid cache (...grr...English heteronyms...), and given that, might as well require it be fresher.

Anyway, suggested changes for v6 (sigh...):

First: you do a second read of vmap_info_gen to optimize out the copy of vmalloc_info if it's easily seen as pointless, but given how small vmalloc_info is (two words!), i'd be inclined to omit that optimization.

Copy always, *then* see if it's worth keeping. Smaller code, faster fast path, and is barely noticeable on the slow path.

Second, and this is up to you, I'd be inclined to go fully non-blocking and only spin_trylock(). If that fails, just skip the cache update.

Third, ANSI C rules allow a compiler to assume that signed integer overflow does not occur. That means that gcc is allowed to optimize "if (x - y > 0)" to "if (x > y)".

Given that gcc has annoyed us by using this optimization in other contexts, It might be safer to make them unsigned (which is required to wrap properly) and cast to integer after subtraction.

Basically, the following (untested, but pretty damn simple):

+/*
+ * Return a consistent snapshot of the current vmalloc allocation
+ * statistics, for /proc/meminfo:
+ */
+void get_vmalloc_info(struct vmalloc_info *vmi)
+{
+ unsigned gen, cache_gen = READ_ONCE(vmap_info_cache_gen);
+
+ /*
+ * The two read barriers make sure that we read
+ * 'cache_gen', 'vmap_info_cache' and 'gen' in
+ * precisely that order:
+ */
+ smp_rmb();
+ *vmi = vmap_info_cache;
+
+ smp_rmb();
+ gen = READ_ONCE(vmap_info_gen);
+
+ /*
+ * If the generation counter of the cache matches that of
+ * the vmalloc generation counter then return the cache:
+ */
+ if (gen == cache_gen)
+ return;
+
+ /* Make sure 'gen' is read before the vmalloc info */
+ smp_rmb();
+ calc_vmalloc_info(vmi);
+
+ /*
+ * All updates to vmap_info_cache_gen go through this spinlock,
+ * so when the cache got invalidated, we'll only mark it valid
+ * again if we first fully write the new vmap_info_cache.
+ *
+ * This ensures that partial results won't be used.
+ */
+ if (spin_trylock(&vmap_info_lock)) {
+ if ((int)(gen - vmap_info_cache_gen) > 0) {
+ vmap_info_cache = *vmi;
+ /*
+ * Make sure the new cached data is visible before
+ * the generation counter update:
+ */
+ smp_wmb();
+ WRITE_ONCE(vmap_info_cache_gen, gen);
+ }
+ spin_unlock(&vmap_info_lock);
+ }
+}
+
+#endif /* CONFIG_PROC_FS */

The only remaining *very small* nit is that this function is a mix of "return early" and "wrap it in an if()" style. If you want to make that "if (!spin_trylock(...)) return;", I leave that you your esthetic judgement.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

[ I don't mind, although I wish other, more critical parts of the kernel got this
much attention as well ;-) ]

Ok, done.

So I'm not sure about this one: we have no guarantee of the order every updater reaches the spinlock, and we want the 'freshest' updater to do the update. The trylock might cause us to drop the 'freshest' update erroneously - so this change would introduce a 'stale data' bug I think.

That's annoying ...

Ok, done.

I've attached v6 which applies your first and last suggestion, but not the trylock one.

I also removed _ONCE() accesses from the places that didn't need them.

I added your Reviewed-by optimistically, saving a v7 submission hopefully ;-)

Lightly tested.

Thanks,

Ingo

==============================>

Er, no it wouldn't. If someone leaves the cache stale, they'll leave vmap_info_cache_gen != vmap_info_gen and the next reader to come along will see the cache is stale and refresh it.

If there's lock contention, there's a risk of more work, because the callers fall back to calc_vmalloc_info rather than waiting.

But it's not a big risk. With the blocking code, if two readers arrive simultaneously and see a stale cache, they'll both call calc_vmalloc_info() and then line up to update the cache.

The second will get the lock but then *not* update the cache.

With trylock(), the second will just skip the update faster. Same number of calc_vmalloc_info() calls.

The only inefficient case is if two readers arrive far enough apart that vmap_info_gen is updated between them, yet close enough together than the second arrives at the lock while the first is updating the cache.

In that case, the second reader will not update the cache and (assuming no more changes to vmap_info_gen) some future third reader will have to duplicate the effort of calling calc_vmalloc_info().

But that's such a tiny window I give preference to my fondness for non-blocking code.

You did right. As I said, the non-blocking part is your preference.

I've done so much nasty stuff in interrupt handlers ($DAY_JOB more than kernel) that I go for the non-blocking algorithm whenever possible.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Since we're beating dead horses, let me point out one possibly unintentional side-effect of initializing just one of vmap_info{,_cache}_gen:

$ nm -n vmlinux | grep -E 'vmap_info(_cache)?_gen'
ffffffff81e4e5e0 d vmap_info_gen
ffffffff820d5700 b vmap_info_cache_gen

[Up-thread, you wrote "I also moved the function-static cache next to the flag and seqlock - this should further compress the cache footprint."]

One should probably ensure that they end up in the same cacheline if one wants the fast-path to be as fast as possible - the easiest way to ensure that is to put them in a small struct, and that might as well contain the spinlock and the cache itself as well.

It's been fun seeing this evolve, but overall, I tend to agree with
Peter: It's a lot of complexity for little gain. If we're not going to just kill the Vmalloc* fields (which is probably too controversial) I'd prefer Linus' simpler version.

Rasmus

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

That's the problem with small, understandable problems: people *aren't* scared to mess with them.

Are you sure you're not being affected by the number of iterations?

The final version is not actually a lot of code (although yes, more than Linus's), and offers the advantage of peace of mind: there's not some nasty-smelling code you can't entirely trust left behind.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Ingo> Ha! :-) Fixed.

Blech, it should be initialized with a proper #define VMAP_CACHE_NEEDS_UPDATE 1, instead of more magic numbers.

Ingo> + */
Ingo> +static DEFINE_SPINLOCK(vmap_info_lock);
Ingo> +static int vmap_info_gen = 1;

   static int vmap_info_gen = VMAP_CACHE_NEEDS_UPDATE;

Ingo> +static int vmap_info_cache_gen; Ingo> +static struct vmalloc_info vmap_info_cache; Ingo> +#endif

This will help keep bugs like this out in the future... I hope!

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Er... this is a joke, right?

First, this number is used exactly once, and it's not part of a collection of similar numbers. And the definition would be adjacent to the use.

We have easier ways of accomplishing that, called "comments".

Second, your proposed name is misleading. "needs update" is defined as vmap_info_gen != vmap_info_cache_gen. There is no particular value of either that has this meaning.

For example, initializing vmap_info_cache_gen to -1 would do just as well. (I actually considered that before deciding that +1 was "simpler" than -1.)

For some versions of the code, an *arbitrary* difference is okay. You could set one ot 0xDEADBEEF and the other to 0xFEEDFACE.

For other versions, the magnitude matters, but not *too* much. Initializing it to 42 would be perfectly correct, but waste time doing 42 cache updates before settling down.

Singling out the value 1 as VMAP_CACHE_NEEDS_UPDATE is actively misleading.

And this is the punchline, right?

The problem was not realizing that non-default initialization was required; what we *call* the non-default value is irrelevant.

I doubt it would ever have been a real (i.e. noticeable) bug, actually; the first bit of vmap activity in very early boot would have invalidated the cache.

(John, my apologies if I went over the top and am contributing to LKML's reputation for flaming. I *did* actually laugh, and *do* think it's a dumb idea, but my annoyance is really directed at unpleasant memories of mindless application of coding style guidelines. In this case, I suspect you just posted before reading carefully enough to see the subtle logic.)

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

George> Er... this is a joke, right?

Not really. The comment made before was that by setting this variable to zero, it wasn't properly initialized. Which implies that either
the API is wrong... or we should be documenting it better. I just
went in the direction of the #define instead of a comment.

George> First, this number is used exactly once, and it's not part of George> a collection of similar numbers. And the definition would be George> adjacent to the use.

George> We have easier ways of accomplishing that, called "comments".

Sure, that would be the better solution in this case.

George> Second, your proposed name is misleading. "needs update" is defined George> as vmap_info_gen != vmap_info_cache_gen. There is no particular value George> of either that has this meaning.

George> For example, initializing vmap_info_cache_gen to -1 would do just as well. George> (I actually considered that before deciding that +1 was "simpler" than -1.)

See, I just threw out a dumb suggestion without reading the patch properly. My fault.

George> (John, my apologies if I went over the top and am contributing to LKML's George> reputation for flaming. I *did* actually laugh, and *do* think it's a George> dumb idea, but my annoyance is really directed at unpleasant memories of George> mindless application of coding style guidelines. In this case, I suspect George> you just posted before reading carefully enough to see the subtle logic.)

Nope, I'm in the wrong here. And your comment here is wonderful, I really do appreciate how you handled my ham fisted attempt to contribute. But I've got thick skin and I'll keep trying in my free time to comment on patches when I can.

John