Allowing small allocations to fail [LWN.net]

Allowing small allocations to fail

Posted Mar 11, 2015 18:26 UTC (Wed) by dlang (guest, #313)
In reply to: Allowing small allocations to fail by roblucid
Parent article: Allowing small allocations to fail

feel free to step back and think of a better way to get the job done. If you find one, many people are going to be interested.

memory overcommit is not your fundamental problem here. In fact, it help avoid the problem the vast majority of the time.

The problem is not userspace applications handling memory failures (I don't understand how the discussion here has focused on userspace), the problem is the kernel allocating memory.

The fundamental problem is that memory is finite, when it's full and you want to write something to disk to free the memory, the process of writing the data out can involve memory allocations (in the filesystem, raid layer, lvm layer, network layer if using iscsi, etc). How do you handle this case?

As discussions have shown, you cannot know ahead of time how much memory these can require, so simply having some reserved memory isn't the answer (at least, it's not that simple to figure out how much memory to reserve)

The deeper the stack of layers that you have to go through to write a chunk of memory out to disk, the more likely you are going to run into problems.

If you use a swap partition on a SATA drive directly, there is far less chance of running into problems that if you are using a swap file on ext4 on top of LVM (with snapshots) on a RAID array connected over iSCSI (which is not an unreasonable setup)

to post comments

Allowing small allocations to fail

Posted Mar 11, 2015 21:19 UTC (Wed) by wahern (subscriber, #37304) [Link] (4 responses)

memory overcommit is not your fundamental problem here. In fact, it help avoid the problem the vast majority of the time.

Isn't this basically the same logic used to justify mapping NULL to a read-only page filled with 0s? Which is what BSD did decades ago. It was a similarly poor design decision from the perspective of resilient systems and it took many years to undo.

Yes, the _majority_ of time you end up with benign behavior. The problem is the cases where you end up with completely wrong behavior. And the only way to solve _all_ the problems was for _everybody_ to write more robust code. The only way to coax code to become more robust was to make it fail spectacularly.

Have we forgotten about the very wise advice, fail fast, fail often?

The problem with overcommit and similar measures is that there's no incentive for people to write robust algorithms. Clearly the XFS people are in this camp. They didn't have to worry about it, so they didn't, and now their code is too complex to change.

You _can_ write robust algorithms resilient against low memory situations. Sometimes it's easy. RAII patterns simplify unwinding state, which is just as easy in C as in C++, minus the automatic destructors. Sometimes it's more difficult and might require rethinking your implementation in terms of an explicit state machine. Other times you must make a tradeoff between CPU cost and memory cost. Linux often already does this--for example using a O(2 log N ), cache-thrashing red-black tree instead of O(1), cache-friendly timing wheel for high resolution timers--but nobody really complains about it not being the absolute fastest possible because raw speed is rarely the _only_ consideration.

Not long ago people said that memory was cheap and worrying about memory constraints was a thing of the past. Then the embedded world exploded.

Properly handling OOM situations in core infrastructure code doesn't solve all the problems. But it's a prerequisite for solving all the problems. And we'll never make any headway as long as people can pass the buck to the OOM killer. The hierarchy of abstraction layers might not be so convoluted and poorly composable if they couldn't rely on simplifying assumption about memory allocation; the interfaces would have to been better designed to make unwinding state easier and make forward progress yieldable at a more fine-grained level.

Look at block devices. The reason we can't have non-blocking disk I/O is because Unix originally made the simplifying assumption that disk writes were per se non-blocking. The assumption was no doubt worthwhile back when it could reduce the complexity of your code by an order of magnitude. But now block device drivers are so complex anyhow that the cost+benefit tradeoff sucks. Same situation wrt to the big kernel lock. I would argue the same thing now applies to the OOM killer. The simplifying assumption has lost it's usefulness, presuming it was ever truly useful.

Allowing small allocations to fail

Posted Mar 11, 2015 21:27 UTC (Wed) by dlang (guest, #313) [Link] (3 responses)

The problem here is not userspace and overcommit. The problem is in the kernel when it needs memory in order to write data to disk to allow it to free memory.

Causing users programs to fail more frequently, in the hope that developers will get better at handling the failures, is not going to make the slightest bit of difference to this problem.

Eliminating the OOM killer isn't going to address the problem of needing memory in order to free memory.

I'll also point out the backlash against ext4 for loosing data when programmers didn't properly use fsync. This isn't perceived by users as being a problem caused by the programmers of the application they are using, it's perceived as being a failure of the kernel.

Allowing small allocations to fail

Posted Mar 11, 2015 22:46 UTC (Wed) by wahern (subscriber, #37304) [Link] (2 responses)

Non-failing allocations in the kernel is part-and-parcel of the OOM killer. The whole point is that some kernel developers assume that if an allocation request fails, the OOM killer will free up some memory.

Of course failing allocations in user space won't fix XFS or other code. It won't fix user space applications, either. (FWIW, malloc could always fail in Linux because of process resource limits.)

But it does change expectations. In an OOM killer world you can make the assumption that if you're called from user space, then a small allocation could never fail because the OOK killer could always kill at least one user space application and thus free up some memory.

Without the OOM killer, XFS would have had to explicitly make arrangements to reserve a bounded amount of memory ahead of time, rather than implicitly relying on fuzzy assumptions.

XFS and similar code exists, and completely refactoring those things is clearly out of the question. But somebody has to pull the short straw and endure a little more pain than the others if and when Linux moves away from the allocations-cannot-fail simplifying assumption.

Allowing small allocations to fail

Posted Mar 12, 2015 0:08 UTC (Thu) by rgmoore (✭ supporter ✭, #75) [Link]

Without the OOM killer, XFS would have had to explicitly make arrangements to reserve a bounded amount of memory ahead of time, rather than implicitly relying on fuzzy assumptions.

I think you have the story backward here, at least in regard to XFS. The XFS developers did exactly what you suggested they should do, and reserved a pool of memory in advance in case memory got really tight. XFS would still work in the case that small allocations were allowed to fail, and they're actually the ones who started pushing to allow them to fail. The problem isn't that XFS never considered what to do if memory was really tight, but that their solution never goes into effect because the triggering case- a failed allocation- isn't allowed to happen.

Allowing small allocations to fail

Posted Mar 12, 2015 0:28 UTC (Thu) by dlang (guest, #313) [Link]

It's far more the case that filesystem developers are doing some really complex things that are really hard to roll back cleanly, and so they assume that some other kernel thread is going to be able to make progress and free some memory than that they assume that the OOM killer will free up memory for them.

I think it's a bad thing that this has grown to be as large and as common as it is. I just don't blame it on overcommit.

Allowing small allocations to fail

Posted Mar 11, 2015 22:12 UTC (Wed) by neilbrown (subscriber, #359) [Link]

> The fundamental problem is that memory is finite,

Amongst the many fundamental problems, the one that stands out to me is that memory is treated as a uniform resource that any code can dip into on a (nearly) equal basis. But different needs really are different, and on more than a high/medium/low priority basis.

There are a class of memory allocations which are only needed for a short period of time. These are the important ones for ensuring forward progress for write-out and freeing memory. They hold network packet headers, or filesystem index blocks that are being updated etc. The grand total amount of memory needed for all of these isn't really very much, and if we had some way to make all these transactions run in sequence - one at a time - you could make solid forward progress with very little memory (it would be slow, but it wouldn't lock-up).

A big issue is that a particular transaction may need to make a sequence of these allocations. The first one will only be genuinely short-lived if all subsequent allocations happen quickly. If a subsequent allocation waits for an earlier allocation to be freed - you deadlock.

mempools are a perfect fit for this need, though they are usually over-provisioned. The pool only really needs one element. Each different allocation needed for a transaction comes from a different mempool. So an allocation from a mempool can only ever block waiting on an allocation in that mempool, or another mempool further downstream, to be freed. This ensures that at least one transaction is always making forward progress.

This is how the block layer works - if you have a stack of block devices (loop over md over dm over SATA), each layer has its own mempools as needed.

But filesystems don't use mempools - mempools have fixed size allocations and filesystems are more complex and can need more variety. So we need something more general.

The big idea here is that the "first" allocation can safely block if there isn't enough space, but "subsequent" allocations must not. "all" we need to do is find a way to associate each allocation with a "transaction". Then we just need to limit the number of transactions that are concurrently active (if memory is tight) and only give the last of the memory to "transaction"-based allocations, and everything will be fine.

The early swap-over-NFS patches had something like this...
See patch 11 of the series linked here: https://lwn.net/Articles/256462/

They we eventually dropped from the series, but the ideas still could be useful.

Allowing small allocations to fail

Posted Mar 11, 2015 22:55 UTC (Wed) by roblucid (guest, #48964) [Link] (1 responses)

> The problem is not userspace applications handling memory failures
> (I don't understand how the discussion here has focused on userspace),
> the problem is the kernel allocating memory.

Simply because in part of the discussion, some suggested system calls returning a failure with ENOMEM, back to userspace.

Allowing small allocations to fail

Posted Mar 12, 2015 0:23 UTC (Thu) by dlang (guest, #313) [Link]

returning ENOMEM to userspace when userspace doesn't know how much memory was needed or why it's needed is a waste of time, and creating a new error code for userspace to look for will mean that existing programs that check error codes now will all be missing the new error code.

Allowing small allocations to fail

Posted Mar 12, 2015 7:44 UTC (Thu) by epa (subscriber, #39769) [Link] (16 responses)

<blockquote>If you use a swap partition on a SATA drive directly, there is far less chance of running into problems that if you are using a swap file on ext4 on top of LVM (with snapshots) on a RAID array connected over iSCSI (which is not an unreasonable setup)</blockquote>The disk setup in itself may not be unreasonable, but for swapping? A RAID array over iSCSI implies a moderately expensive server system. Surely if swap space is required, an SATA disk could be plugged into the local motherboard for that purpose.

In other words is the extra complexity of allowing swap files on a filesystem, rather than raw swap partitions, still needed? Swap space was a big deal twenty years ago but while it is still needed today it has diminished in importance a bit.

Allowing small allocations to fail

Posted Mar 12, 2015 7:55 UTC (Thu) by dlang (guest, #313) [Link] (3 responses)

many servers don't have any local storage (I forgot to add the hypervisor layer in my example to top things off)

Personally, I operate servers with minimal or no swap, but the people who are screaming about how evil overcommit and copy-on-write are need to have a LOT of swap so that they can pretend that it's real memory when a program forks.

Oh, by the way, they are still betting that it's never going to be needed, because if it actually was needed, the system would be unusable. I'd rather have a system fail, even if it triggers the OOM killer (which does log what it's doing, so my central log system can detect failures, including the failure of the log forwarder), rather than slow to a crawl but still appear to be working.

Allowing small allocations to fail

Posted Mar 13, 2015 7:03 UTC (Fri) by epa (subscriber, #39769) [Link] (2 responses)

...and so we come back to fork() being the wrong tool for the job 90% of the time (since most fork() is just a precursor to exec()) and how userspace should use posix_spawn() instead where possible, except that sometimes you need to do extra manipulations in the child process before exec(), but even then a whole copy of the parent's address space is not usually needed...

Allowing small allocations to fail

Posted Mar 17, 2015 18:54 UTC (Tue) by nix (subscriber, #2304) [Link] (1 responses)

posix_spawn() is insanely complex, hard to use, very *rarely* used and has as a result had serious bugs in the past. It's best avoided unless you expect your program to be useful on a box without an MMU.

Allowing small allocations to fail

Posted Mar 18, 2015 9:58 UTC (Wed) by cesarb (subscriber, #6266) [Link]

> It's best avoided unless you expect your program to be useful on a box without an MMU.

Isn't it also useful if you expect your program to be ported to operating systems without fork()/exec() (Windows) or operating systems where the GUI libraries don't like fork() (from what I've heard, this is the case on Mac)?

Allowing small allocations to fail

Posted Mar 13, 2015 1:02 UTC (Fri) by neilbrown (subscriber, #359) [Link] (11 responses)

> In other words is the extra complexity of allowing swap files on a filesystem, rather than raw swap partitions, still needed?

There is very little extra complexity here.
When you enable swap on a (non-NFS) filesystem, the kernel uses 'bmap' to find where all the blocks in the file are, ignores any fragments that aren't nicely page-sized, and then swaps to the block device using that list of addresses.

This is one reason that BTRFS doesn't support swap files. Files don't have a fixed address on just one block device.

The complexity in the example you cite doesn't come from the fact that a 'file' is used. LVM and RAID are pretty safe too - there is complexity there, but they handle it just fine because they have to.

I really don't know about iSCSI. To my mind it is by far the most complex part of the stack. But this may simply because I haven't looked at the code - maybe it works perfectly already.

Allowing small allocations to fail

Posted Mar 13, 2015 1:29 UTC (Fri) by dlang (guest, #313) [Link] (10 responses)

It's not that the layers are bad, just that getting the data out requires involving all the layers, and any of them can end up needing memory to get things done. At the very least, having many layers involved can cause allocations that would otherwise be short-lived end up being needed longer.

Similar to the way that these different layers can consume stack space to the point that the system gets in trouble (and working to move things off of the stack requires other allocations)

Allowing small allocations to fail

Posted Mar 13, 2015 1:57 UTC (Fri) by neilbrown (subscriber, #359) [Link] (9 responses)

With respect ... I think you are guessing. You are identifying things that you think could go wrong. Not things that actually go wrong.

Multiple layers of block devices do not use extra stack. When one layer sends a request to the next layer, the request is queued at a higher stack level, and not processed until the first block device's code has vacated the stack.

"more layers needs more memory" isn't really a good characterization of the sort of problems we can run in to. There really is plenty of memory, just like there are plenty of chopsticks for the dining philosophers. A bit of communication and sensible sharing is all you need.

Somewhat tangentially.... I'm also somewhat perplexed by the various mentions of returning ENOMEM errors to user-space. In my mind that is TOTALLY different conversation than talk about reserving memory to ensure progress when writing out dirty data.

-ENOMEM really isn't something that user-space should ever see for the vast majority of system calls. When code handling a systemcall needs a modest-sized allocation, waiting indefinitely is the right thing to do (maybe after dropping some locks).

Conversely when handling write-out, it is only appropriate to wait if you *know* that memory will be released that you *will* get access to.

Allowing small allocations to fail

Posted Mar 13, 2015 3:16 UTC (Fri) by dlang (guest, #313) [Link] (1 responses)

I use stack space ans an example after seeing the repeated discussions of "XFS + <layers> runs out of stack space" discussions on linux-kernel. I can't talk in detail about the issue, but I know from watching this that the different layers are not as isolated in their effects as you make it sound.

As for the layers, yes, I am saying that these layers can cause things to go wrong, not that they will cause problems. Raid, encryption, compression, snapshots can all require reading in data from disk in order to write data out to disk. Filesystem operations can require read-modify-write cycles that can require memory for the read, iscsi invokes the entire networking stack and needs memory to encapsulate the I/O data, etc.

When the kernel picks a hunk of memory to output to disk (either swap or pending writes), it has no way of knowing what is going to be involved to write this data out. It may be that all of these layers have sufficient memory pre-allocated that they never, ever need to allocate more during the running of the system, but I really have my doubts. I know that at least some of them have enough reserved memory that they can limp along to complete a single request if they can't get a normal allocation, but with the 'too small to fail' logic having been in place, how many of these emergency codepaths have really been tested? And are the allocations ending up in the 'blocking, waiting to succeed' mode when the programmer has actually coded a good failure mode and way to make at least some progress even without the allocation?

The stack I listed above was an off-the-cuff 'bad case', but as people have been challenging it, I've been thinking and don't think it's anywhere near the real worst case.

I can easily see someone having
filesystem
raid
lvm
snapshot
encryption
fuse
virtualization
network (with connection tracking and encryption on the network)

with the possibility that some of these layers may be repeated on the hypervisor level (which shouldn't contribute to memory issues in the guest, but guests could contribute to issues on the host)

I'm probably still not getting the real worst-case situation (it would be interesting to see not just speculation, but real-world information, I'll bet that real-world examples will make the speculation look good)

Allowing small allocations to fail

Posted Mar 14, 2015 6:05 UTC (Sat) by neilbrown (subscriber, #359) [Link]

> I know that at least some of them have enough reserved memory that they can limp along to complete a single request if they can't get a normal allocation, but with the 'too small to fail' logic having been in place, how many of these emergency codepaths have really been tested?

Lots of them.

"too small to fail" doesn't apply to all kernel allocations. It does apply to those with the GFP_KERNEL flags set, but not, for example, those with GFP_ATOMIC.

Any code that has been written with a clear emergency fallback almost certainly uses an allocation style that can fail - if it didn't there is a very good chance that it would deadlock. mempools, for example, always set __GFP_NORETRY, so normal allocation *will* fail if no memory is easily available, and the fall-back to the pre-allocated pools is often used.

GFP_NOFS allocations are probably the most problematic. I think they can be treated as "too small to fail", but there can be lots of dirty memory that they cannot touch.

Of all the things in your stack, I think filesystems, fuse, and networking are the most likely to have interesting issues: filesystems because they are complex, fuse because it can depend on userspace behaving correctly, and networking because it is highly optimized for speed and tries to avoid special cases on the fast-paths.
All these can be made to work well, but the problems they might face are really quite independent of what other things in the stack might be doing.

Allowing small allocations to fail

Posted Mar 13, 2015 7:08 UTC (Fri) by epa (subscriber, #39769) [Link] (6 responses)

Waiting and retrying for an allocation failure is fair enough, but waiting indefinitely? Surely it's better to inform userspace of the failure so a well-written program can take some appropriate action, rather than just hanging the whole userspace process or thread.

Allowing small allocations to fail

Posted Mar 13, 2015 7:35 UTC (Fri) by dlang (guest, #313) [Link] (2 responses)

so what do you do when you can't notify userspace? For example, a memory allocation failure when you are trying to write data to disk and the program that created the data has already exited.

Allowing small allocations to fail

Posted Mar 13, 2015 7:35 UTC (Fri) by dlang (guest, #313) [Link]

remember that these 'too small to fail' allocations are allocations made by the kernel, not ones made by userspace via malloc or similar.

Allowing small allocations to fail

Posted Mar 13, 2015 16:08 UTC (Fri) by epa (subscriber, #39769) [Link]

The general principle is to notify the caller. If the caller was a userspace program that made a system call, and the system call can't complete because there isn't enough memory, you return a failure status such as ENOMEM. If the caller was a kernel routine, again you return the failure status. In neither case is hanging indefinitely really a sensible thing to do - although certainly a limited amount of waiting and retrying can be a good idea.

Allowing small allocations to fail

Posted Mar 14, 2015 5:44 UTC (Sat) by neilbrown (subscriber, #359) [Link] (2 responses)

> Waiting and retrying for an allocation failure is fair enough, but waiting indefinitely?

To know whether or not it is reasonable to wait indefinitely, you need to have a clear idea of what you are waiting for. You are obviously waiting for something to be freed.

We can classify users of kernel memory in various ways, but one would be:

- permanent allocations which will never be freed, normally made a boot time. These don't affect how you wait.
- caches. If the system is working, these will eventually shrink to a reasonable size. You need to wait for that.
- stack/heap memory of processes (i.e. "anonymous memory"). These can be released by the OOM killer as a last resort, which might take a while to decide the time has come.
- other kernel objects that are refcounted and freed when not in use. There are limits on all of these (such as the limit on number of open filedescriptors), so the total memory used by these should not get out of control. We never wait for these.

The only two of these that can really exhaust memory are the caches and the anonymous memory. On a properly managed system, the total of anonymous pages will not approach the total of swap+physical memory, so you just need to wait for the caches to flush. That is an indefinite wait, but not an infinite wait.
On a misbehaving system, you might need to wait for the OOM killer to do its job - which is a hard job and may not be quick.

So yes: I think "indefinite waits" are entirely appropriate for code that is not cleaning out a cache or part of the OOM killer. For code that is, carefully prioritized memory reservations are needed.

Allowing small allocations to fail

Posted Mar 14, 2015 7:36 UTC (Sat) by dlang (guest, #313) [Link] (1 responses)

one other category of allocations is memory used by programs that may finish running and exit, freeing memory

Allowing small allocations to fail

Posted Mar 17, 2015 18:59 UTC (Tue) by nix (subscriber, #2304) [Link]

Neil covered those: they're either anonymous memory or memory in the cache.