Not logged in
Log in now
Create an account
Subscribe to LWN
Pencil, Pencil, and Pencil
Dividing the Linux desktop
LWN.net Weekly Edition for June 13, 2013
A report from pgCon 2013
Little things that matter in language design
No, what vmware is doing is not stupid. The security "concern" is not a
concern. One simply does a memcmp on pages which have a matching hash.
The result of the KSM hash avoidance _will_ be a slower, less scalable
identical page scanning mechanism. The stable/unstable lists optimisation
is orthogonal to the use of hashes.
See? Patents do help foster innovation!
Posted May 3, 2009 15:00 UTC (Sun) by dion (subscriber, #2764)
Posted May 8, 2009 9:34 UTC (Fri) by muwlgr (guest, #35359)
Contrary, when you compare pages by their contents right from the start, in most cases you could find differing pages quite quickly, by reading only their first few bytes. You have to read two whole pages only to find out that they are identical. And this is done without mathematical overhead of hash calculation, remember. So your memory traffic is 100% only for those pages that happen to be identical. For pages that are different pairwise, you usually have to read only a small part of them to find that. With random contents of the pages, you stop comparing them on the first byte in 255/256 cases. On the fourth byte (32-bit word), in (2^32-1)/2^32 cases. In Linux case, there could exist differing pages with longer common prefixes, but I think this prefix will be shorter than half of page length often enough. So for differing memory pages you most probably don't get 100% of memory traffic anyway. I clearly see why simplified approach of KSM could have its benefits.
Posted May 8, 2009 10:50 UTC (Fri) by efexis (guest, #26355)
Posted May 8, 2009 14:19 UTC (Fri) by nix (subscriber, #2304)
Posted May 15, 2009 19:43 UTC (Fri) by nevyn (subscriber, #33129)
We can avoid reading the whole page for each comparison, even in the worst case.
Posted Nov 17, 2009 16:03 UTC (Tue) by gmatht (guest, #58961)
This is clearly very inefficient, as this simple algorithms needs exactly
(4096*8) branches to find any page. However we read the page exactly once
for all comparisons. And we can optimize it, e.g. if we have a chain of
nodes with only single children we can merge them into a single edge.
Another approach would be to make use of the fact that if say, we know all
child pages of the current node start with "Foo" we don't need to compare
the first 3 characters anymore. As such, we'd usually only have to access
each cache-line once.
Copyright © 2013, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds