first day coverage
This article covers the second day of the 2011 Linux Filesystem, Storage,
and Memory Management Summit, held on April 5, 2011 in San Francisco,
California. Those who have not yet seen the
may want to have a look
before continuing here.
The opening plenary session was led by Michael Cornwall, the global
director for technology standards at IDEMA, a standards organization for disk
drive manufacturers. His talk, which was discussed in a separate article, covered the changes
that are coming in the storage industry and how the Linux community can get
involved to make things work better.
I/O resource management
The main theme of the memory management track often appeared to be "control
groups"; for one session, though, the entire gathering got to share the control
group fun as Vivek Goyal, Fernando Cao, and Chad Talbott led a discussion on
I/O bandwidth management. There are two I/O bandwidth controllers in the
kernel now: the throttling controller (which can limit control groups to an
absolute bandwidth value) and the proportional controller (which divides up
the available bandwidth between groups according to an administrator-set
policy). Vivek was there to talk about the throttling controller, which is
in the kernel and working, but which still has a few open issues.
One of those is that the throttling controller does not play entirely well
with journaling filesystems. I/O ordering requirements will not allow the
journal to be committed before other operations have made it to disk; if
some of those other operations have been throttled by the controller, the
journal commit stalls and the
whole filesystem slows down. Another is that the controller can only
manage synchronous writes; writes which have been buffered through the page
cache have lost their association with the originating control group and
cannot be charged against that group's quota. There are patches to perform throttling of buffered
writes, but that is complicated and intrusive work.
Another problem was pointed out by Ted Ts'o: the throttling controller
applies bandwidth limits on a per-device basis. If a btrfs filesystem is
in use, there may be multiple devices which make up that filesystem. The
administrator would almost certainly want limits to apply to the volume
group as a whole, but the controller cannot do that now. A related problem
is that some users want to be able to apply global limits - limits on the
amount of bandwidth used on all devices put together. The throttling
controller also does not work with NFS-mounted filesystems; they have no
underlying device at all, so there is no place to put a limit.
Chad Talbott talked about the proportional bandwidth controller; it works
well with readers and synchronous writers, but, like the throttling
controller, it is unable to deal with asynchronous writes. Fixing that
will require putting some control group awareness into the per-block-device
flushing threads. The system currently maintains a set of per-device lists
containing inodes with dirty pages; those lists need to be further
subdivided into per-control-group lists to enable the flusher threads to
write out data according to the set policy. This controller also does not
yet properly implement hierarchical group scheduling, though there are patches out there to add that functionality.
The following discussion focused mostly on whether the system is
accumulating too many control groups. Rather than a lot of per-subsystem
controllers, we should really have a cross-subsystem controller mechanism.
At this point, though, we have the control groups (and their associated
user-space API which cannot be broken) that are in the kernel. So, while
some (like James Bottomley) suggested that we should maybe dump the
existing control groups in favor of something new which gets it right, that
will be a tall order. Beyond that, as Mike Rubin pointed out, we don't
really know how control groups should look even now. There has been a lack
of "taste and style" people to help design this interface.
Working set estimation
Back in the memory management track, Michel Lespinasse discussed Google's
working set estimation code. Google has used this mechanism for some time
as a way of optimally placing new jobs in its massive cluster. By getting
a good idea of how much memory each job is really using, they can find the
machines with the most idle pages and send new work in that direction.
Working set estimation, in other words, helps Google to make better
decisions on how to overcommit its systems.
The implementation is a simple kernel thread which scans through the
physical pages on the system, every two minutes by default. It looks at
each page to determine whether it has been touched by user space or not and
remembers that state. The whole idea is to try to figure out how many
pages could be taken away from the system without causing undue memory
pressure on the jobs running there.
The kernel thread works by setting a new "idle" flag on each page which
looks like it has not been referenced. That bit is cleared whenever an
actual reference happens (as determined by looking at whether the VM
subsystem has cleared the "young" bit). Pages which are still marked idle
on the successive scan are deemed to be unused. The estimation code does
not take any action to reclaim those pages; it simply exports statistics
on how many unused pages there are through a control group file. The
numbers are split up into clean, swap-backed dirty, and file-backed dirty
pages. It's then up to code in user space to decide what to do with that
There were questions about the overhead of the page scanning; Michel said
that scanning every two minutes required about 1% of the available CPU
time. There were also questions about the daemon's use of two additional
page flags; those flags are a limited resource on 32-bit systems. It was
suggested that a separate bitmap outside of the page structure
could be used. Google runs everything in 64-bit mode, though, so there has
been little reason to care about page flag exhaustion so far. Rik van Riel
suggested that the feature could simply not be supported on 32-bit
systems. He also suggested that the feature might be useful in other
contexts; systems running KVM-virtualized guests could use it to control
the allocation of memory with the balloon driver, for example.
Virtual machine sizing
Rik then led a discussion on a related topic: allocating the right amount
of memory to virtual machines. As with many problems, there are two
distinct aspects: policy (figuring out what the right size is for any given
virtual machine) and mechanism (actually implementing the policy
decisions). There are challenges on both sides.
There are a number of mechanisms available for controlling the memory
available to a virtual machine. "Balloon drivers" can be used to allocate
memory in guests and make it available to the host; when a guest needs to
get smaller, the balloon "inflates," forcing the guest to give up some
pages. Page hinting is a mechanism by
which the guest can inform the host that certain pages do not contain
useful data (for example, they are on the guest's free list). The host can
then reclaim memory used for so-hinted pages without the need to write them
out to backing store. The host can also simply swap the guest's pages out
without involving the guest operating system at all. The KSM mechanism allows the kernel to recover
pages which contain duplicated contents. Compression can be used to cram
data into a smaller number of pages. Page contents can also simply be
moved around between systems or stashed into some sort of transcendent
There seem to be fewer options on the policy side. The working set
estimation patches are certainly one possibility. One can control memory
usage simply through decisions on the placement of virtual machines. The
transcendent memory mechanism also allows the host to make policy decisions
on how to allocate its memory between guests.
One interesting possibility raised by Rik was to make the balloon mechanism
better. Current balloon drivers tend to force the release of random pages
from the guest; that leads to fragmentation in the host, thwarting attempts
to use huge pages. A better approach might be to use page hinting,
allowing the guest to communicate to the host which pages are free. The
balloon driver could then work by increasing the free memory thresholds
instead of grabbing pages itself; that would force the guest to keep more
pages free. Even better, memory compaction would come into play, so the
guest would be driven to free up contiguous ranges of pages. Since those
pages are marked free, the host can grab them (hopefully as huge pages) and
use them elsewhere. With this approach, there is no need to pass pages
directly to the host; the hinting is sufficient.
There are other reasons to avoid the direct allocation of pages in balloon
drivers; as Pavel Emelyanov pointed out, that approach can lead to
out-of-memory situations in the guest. Andrea Arcangeli stated that, when
balloon drivers are in use, the guest must be configured with enough swap
space to avoid that kind of problem; otherwise things will not be stable.
The policy implemented by current balloon drivers is also entirely
determined by the host system; it's not currently possible to let the guest
decide when it needs to grow.
There is also a simple problem of communication; the host has no
comprehensive view of the memory needs of its guest systems. Fixing that
problem will not be easy; any sort of intrusive monitoring of guest memory
usage will fail to scale well. And most monitoring tends to fall down when
a guest's memory usage pattern changes - which happens frequently.
Few conclusions resulted from this session. There will be a new set of
page hinting patches from Rik in the next few weeks; after that, thought
can be put into doing ballooning entirely through hinting without having to
call back to the host.
Dirty limits and writeback
The memory management track had been able to talk for nearly a full hour
without getting into control groups, but that was never meant to last; Greg
Thelen brought the subject back during his session on the management of
dirty limits within control groups. He made the claim that keeping track
of dirty memory within control groups is relatively easy, but then spent
the bulk of his session talking about the subtleties involved in that
The main problem with dirty page tracking is a more general memory
controller issue: the first control group to touch a specific page
gets charged for it, even if other groups make use of that page later.
Dirty page tracking makes that problem worse; if control group "A" dirties
a page which is charged to control group "B", it will be B which is charged
with the dirty page as well. This behavior seems inherently unfair; it
could also perhaps facilitate denial of service attacks if one control
group deliberately dirties pages that are charged to another group.
One possible solution might be to change the ownership of a page when it is
dirtied - the control group which is writing to the page would then be
charged for it thereafter. The problem with that approach is pages which
are repeatedly dirtied by multiple groups; that could lead to the page
bouncing back and forth. One could try a "charge on first dirty" approach,
but Greg was not sure that it's all worth it. He does not expect that
there will be a lot of sharing of writable pages between control groups in
the real world.
The bigger problem is what to do about control groups which hit their dirty
limits. Presumably they will be put to sleep until their dirty page counts
go below the limit, but that will only work well if the writeback code
makes a point of writing back pages which are associated with those control
groups. Greg had three possible ways of making that happen.
The first of those involved creating a new memcg_mapping structure
which would take the place of the address_space structure used to
describe a particular mapping. Each control group would have one of these
structures for every mapping in which it has pages. The writeout code
could then find these mappings to find specific pages which need to be
written back to disk. This solution would work, but is arguably more
complex than is really needed.
An approach which is "a little dumber" would have the system associating
control groups with inodes representing pages which have been dirtied by
those control groups. When a control group goes over its limit, the system
could just queue writeback on the inodes where that group's dirty pages
reside. The problem here is that this scheme does not handle sharing of
inodes well; it can't put an inode on more than one group's list. One
could come up with a many-to-one mechanism allowing the inode to be
associated with multiple control groups, but that code does not exist now.
Finally, the simplest approach is to put a pointer to a memory control
group into each inode structure. When the writeback code scans through the
list of dirty inodes, it could simply skip those which are not associated
with control groups that have exceeded their dirty limit. This approach,
too, does not do sharing well; it also suffers from the disadvantage that
it causes the inode structure to grow.
Few conclusions were reached in this session; it seems clear that this code
will need some work yet.
Kernel memory accounting and soft limits
The kernel's memory control group mechanism is concerned with limiting
user-space memory use, but kernel memory can matter too. Pavel Emelyanov
talked briefly about why kernel memory is important and how it can be
tracked and limited. The "why" is easy; processes can easily use
significant amounts of kernel memory. That usage can impact the system in
general; it can also be a vector for denial of service attacks. For
example, filling the directory entry (dentry) cache is just a matter of
writing a loop running "mkdir x; cd x". For as long as
that loop runs, the entire chain of dentries representing the path to the
bottommost directory will be pinned in the cache; as the chain grows, it
will fill the cache and prevent anything else from performing path
Tracking every bit of kernel data used by a control group is a difficult
job; it also becomes an example of diminishing returns after a while. Much
of the problem can be solved by looking at just a few data structures.
Pavel's work has focused on three structures in particular: the dentry
cache, networking buffers, and page tables. The dentry cache controller is
relatively straightforward; it can either be integrated into the memory
controller or made into a separate control group of its own.
Tracking network buffers is harder due to the complexities of the TCP
protocol. The networking code already does a fair amount of tracking,
though, so the right solution here is to integrate with that code to create
a separate controller.
Page tables can occupy large amounts of kernel memory; they present some
challenges of their own, especially when a control group hits its limit.
There are two ways a process can grow its page tables; one is via system
calls like fork() or mmap(). If a limit is hit there,
the kernel can simply return ENOMEM and let the process respond as
it will. The other way, though, is in the page fault handler; there is no
way to return a failure status there. The best the controller can do is to
send a segmentation fault signal; that usually just results in the
unexpected death of the program which incurred the page fault. The only
alternative would be to invoke the out-of-memory killer, but that may not
even help: the OOM killer is designed to free user-space memory, not kernel
Pavel plans to integrate the page table tracking into the memory
controller; patches are forthcoming.
Ying Han got a few minutes to discuss the implementation of soft limits in
the memory controller. As had been mentioned on the first day, soft limits
differ from the existing (hard) limits in that they can be exceeded if the
system is not under global memory pressure. Once memory gets tight, the
soft limits will be enforced.
That enforcement is currently suboptimal, though. The code maintains a
red-black tree in each zone containing the control groups which are over
their soft limits, even though some of those groups may not have
significant amounts of memory in that specific zone. So the system needs
to be taught to be more aware of allocations in each zone.
The response to memory pressure is also not perfect; the code picks the
control group which has exceeded its soft limit by the largest amount and
beats on it until it goes below the soft limit entirely. It would probably
be better to add some fairness to the algorithm and spread the pain among
all of the control groups which have gone over their limits. Some sort of
round-robin algorithm which would cycle through those groups would probably
be a better way to go.
There was clearly more to discuss on this topic, but time ran out and the
discussion had to end.
Transparent huge page improvements
Andrea Arcangeli had presented the transparent huge page (THP) patch set at the
2010 Summit and gotten some valuable feedback in return. By the 2011
event, that code had been merged for the 2.6.38 kernel; it still had a
number of glitches, but those have since been fixed up. Since then, THP
has gained some improved statistics support under /proc; there is
also an out-of-tree patch to add some useful information to
/proc/vmstat. Some thought has been put into optimizing libraries
and applications for THP, but there is rarely any need to do that;
applications can make good use of the feature with no changes at all.
There are a number of future optimizations on Andrea's list, though he made
it clear that he does not plan to implement them all himself. The first
item, though - adding THP support to the mremap() system call -
has been completed. Beyond that, he would like to see the process of
splitting huge pages optimized to remove some unneeded TLB flush
operations. The migrate_pages() and move_pages() system
calls are not yet THP-aware, so they split up any huge pages they are asked
to move. Adding a bit of THP awareness to glibc could improve performance
The big item on the list is THP support for pages in the page cache;
currently only anonymous pages are supported. There would be some big
benefits beyond another reduction in TLB pressure; huge pages in the page
cache would greatly reduce the number of pages which need to be scanned by
the reclaim code. It is, however, a huge job which would require changes
in all filesystems. Andrea does not seem to be in a hurry to jump into
that task. What might happen first is the addition of huge page support to
the tmpfs filesystem; that, at least, would allow huge pages to be used in
shared memory applications.
Currently THP only works with one size of huge pages - 2MB in most
configurations. What about adding support for 1GB pages as well? That
seems unlikely to happen anytime soon. Working with those pages would be
expensive - a copy-on-write fault on a 1GB page would take a long time to
satisfy. The code changes would not be trivial; the buddy allocator cannot
handle 1GB pages, and increasing MAX_ORDER (which determines the
largest chunk managed by the buddy allocator) would not be easy to do.
And, importantly, the
benefits would be small to the point that they would be difficult to
measure. 2MB pages are enough to gain almost all of the performance
benefits which are available, so supporting larger page sizes is almost
certainly not worth the effort. The only situation in which is might
happen is if 2MB pages become the basic page size for the rest of the
Might a change in the primary page size happen? Not anytime soon. Andrea
actually tried it some years ago and ran into a number of problems. Among
other things, a larger page size would change a number of system call
interfaces in ways which would break applications. Kernel stacks would
become far more expensive; their implementation would probably have to
change. A lot of memory would be wasted in internal fragmentation. And a
lot of code would have to change. One should not expect a page size change
to happen in the foreseeable future.
Non-uniform memory access systems are characterized by the fact that some
memory is more expensive to access than the rest. For any given node in
the system, memory which is local to that node will be faster than memory
found elsewhere in the system. So there is a real advantage to keeping
processes and their memory together. Rik van Riel made the claim that this
is often not happening. Long-running processes, in particular, can have
their memory distributed across the system; that can result in a 20-30%
performance loss. He would like to get that performance back.
His suggestion was to give each process a "home node" where it would run if
at all possible. The home node differs from CPU affinity in that the
scheduler is not required to observe it; processes can be migrated away
from their home node if necessary. But, when the scheduler performs load
balancing, it would move processes back to their homes whenever possible.
Meanwhile, the process's memory allocations would be performed on the home
node regardless of where the process is running at the time. The end
result should be processes running with local memory most of the time.
There are some practical difficulties with this scheme, of course. The
system may end up with a mix of processes which all got assigned to the
same home node; there may then be no way to keep them all there. It's not
clear what should happen if a process creates more threads than can be
comfortably run on the home node. There were also concerns about
predictability; the "home node" scheme might create wider variability
between identical runs of a program. The consensus, though, was that speed
beats predictability and that this idea is worth experimenting with.
What happens if a process (or the kernel) modifies the contents of a page
in the time between when that page is queued for writing to persistent
storage and when the hardware actually performs the write? Normally, the
result would be that the newer data is written, and that is not usually a
problem. If, however, something depends on the older contents, the result
could be problematic. Examples which have come up include checksums used
for integrity checking or pages which have been compressed or encrypted.
Changing those pages before the I/O completes could result in an I/O
operation failure or corrupted data - neither of which is desirable.
The answer to this problem is "stable pages" - a rule that pages which are
in flight cannot be changed. Implementing stable pages is relatively easy
(with one exception - see below). Pages which are written to persistent
storage are already marked read-only by the kernel; if a process tries to
write to the page, the kernel will catch the fault, mark the page
(once again) dirty, then allow the write to proceed. To implement stable
pages, the kernel need only force that process to block until any
outstanding I/O operations have completed.
The btrfs filesystem implements stable pages now; it needs them for a number
of reasons. Other filesystems do not have stable pages, though; xfs and
OCFS implement them for metadata only, and the rest have no concept of
stable pages at all. There has been some resistance to the idea of adding
stable pages because there is some fear that performance could suffer;
processes which could immediately write to pages under I/O would slow down
if they are forced to wait.
The truth of the matter seems to be that most of the performance worries
are overblown; in the absence of a deliberate attempt to show problems, the
performance degradation is not measurable. There are a few exceptions;
applications using the Berkeley database manager seem to be one example.
It was agreed that it would be good to have some better measurements of
potential performance issues; a tracepoint may be placed to allow
developers to see how often processes are actually blocked waiting for
pages under I/O.
It turns out that there is one place where implementing stable pages is
difficult. The kernel's get_user_pages() function makes a range
of user-space pages accessible to the kernel. If write access is
requested, the pages are made writable at the time of the call. Some time
may pass, though, before the kernel actually writes to those pages; in the
meantime, some of them may be placed under I/O. There is currently no way
to catch this particular race; it is, as Nick Piggin put it, a real
There was some talk of alternatives to stable pages. One is to use bounce
buffers for I/O - essentially copying the page's contents elsewhere and
using the copy for the I/O operation. That would be expensive, though, so
the idea was not popular. A related approach would be to use
copy-on-write: if a process tries to modify a page which is being written,
the page would be copied at that time and the process would operate on the
copy. This solution may eventually be implemented, but only after stable
pages have been shown to be a real performance problem. Meanwhile, stable
pages will likely be added to a few other filesystems, possibly controlled
by a mount-time option.
Toward the end of the day, Qian Cai discussed the problem of sustainable
testing. There are a number of ways in which our testing is not as good as
it could be. Companies all have their own test suites; they duplicate a
lot of effort and tend not to collaborate in the development of the tests
or sharing of the results. There are some public test suites (such as
xfstests and the Linux Testing Project), but they don't work together and
each have their own approach to things. Some tests need specific hardware
which may not be generally available. Other tests need to be run manually,
reducing the frequency with which they are run.
The subsequent discussion ranged over a number of issues without resulting
in any real action items. There was some talk of error injection; that was
seen as a useful feature, but a hard thing to implement well. It was said
that our correctness tests are in reasonably good shape, but that there are
fewer stress tests out there. The xfstests suite does some stress testing,
but it runs for a relatively short period of time so it cannot catch memory
leaks; xfstests is also not very useful for catching data corruption
The biggest problem, though, is one which has been raised a number of times
before: we are not very good at catching performance regressions. Ted Ts'o
stated that the "dirty secret" is that kernel developers do not normally
stress filesystems very much, so they tend not to notice performance
In the final set of lightning talks, Aneesh Kumar and Venkateswararao
Jujjuri talked about work which is being done with the 9p filesystem. Your
editor has long wondered why people are working on this filesystem, which
originally comes from the Plan9 operating system. The answer was revealed
here: 9p makes it possible to export filesystems to virtualized guests in a
highly efficient way. Improvements to 9p have been aimed at that use case;
it now integrates better with the page cache, uses the virtio framework to
communicate with guests, can do zero-copy I/O to guests running under QEMU,
and supports access control lists. The code for all this is upstream and
will be shipping in some distributions shortly.
Amir Goldstein talked about his snapshot
code, which now works with the ext4 filesystem. The presentation
consisted mostly of benchmark results, almost all of which showed no
significant performance costs associated with the snapshot capability. The
one exception appears to be the postmark benchmark, which performs a lot of
Mike Snitzer went back to the "advanced format" discussion from the
morning's session on future technology. "Advanced format" currently means
4k sectors, but might the sector size grow again in the future? How much
pain would it take for Linux to support sector sizes which are larger than
the processor's page size? Would the page size have to grow too?
The answer to the latter question seems to be "no"; there is no need or
desire to expand the system page size to support larger disk sectors.
Instead, it would be necessary to change the mapping between pages in
memory and sectors on the disk; in many filesystems, this mapping is still
done with the buffer head structure. There are some pitfalls, including
proper handling of sparse files and efficient handling of page faults, but
that is just a matter of programming. It was agreed that it would be nice
to do this programming in the core system instead of having each filesystem
solve the problems in its own way.
The summit concluded with an agreement that things had gone well, and that
the size of the event (just over 70 people) was just about right. The
summit, it said, should be considered mandatory for all maintainers working
in this area. It was also agreed that the memory management developers
(who have only been included in the summit for the last couple of meetings)
should continue to be invited. That seems inevitable for the next summit;
the head of the program committee, it was announced, will be memory
management hacker Andrea Arcangeli.
to post comments)