2
$\begingroup$

In ext4 file system, the files are spaced out as far apart as reasonably possible to allow for efficient reallocation. Why do we not do this in memory?

Why not allocate one memory as page 20, and the next large allocation as page 100 to allow for excess expansion before and after the current allocation? I feel that makes sense for large frequently changing-in-size buffers. For smaller buffers, doing so would probably be a drain on memory because we have to allocate each page for a small amount of bytes(but perhaps do it within a block too in the malloc impl). This would also provide greater memory corruption prevention, allowing segfaults(or windows equivalent) to happen quicker(specifically for larger buffers).

Why don't we do this? I get it on modern 32-bit systems because of limited address space, but why not on 64-bit?

$\endgroup$
  • $\begingroup$ @Evil I was thinking about that, I imagine a malloc implementation where you specify an optimized maximum(not absolute, it could be moved), which could be TB(or more) for all a 64-bit virtual memory space cares. We could also just assume an amount equal to the size of maximum size of memory available to the program before and after the buffer because we have so much address space. $\endgroup$ – JavaProphet Jul 23 '16 at 0:51
  • $\begingroup$ @Evil I don't know where you get this division from. There is little to no need to optimize small allocations, the standard shove them all in a few pages is fine, we can always move them to large buffer optimizations if they are needed. What do you mean cannot use half of your memory? I don't understand what your saying. $\endgroup$ – JavaProphet Jul 23 '16 at 0:56
  • $\begingroup$ @Evil I think it's a good idea to run ideas by people who have more experience than me, in the event that it's been thought of and decided a bad idea before. I think that based on some arbitrary amount, if less than, store with a conventional; if greater than, store with this expandable method. Doing a realloc to resize before the buffer rather than after it would require a new function call, so not be compatible with working impls too. $\endgroup$ – JavaProphet Jul 23 '16 at 1:07
  • $\begingroup$ I deleted my comments, please see the answer - it covers the core of the problem. Anyway, I still feel a bit concerned about scattering data in memory - I mean there is always trade off and when some length of buffers is arbitrary chosen and I dislike the outcomes. $\endgroup$ – Evil Jul 23 '16 at 1:31
2
$\begingroup$

Why is memory different from a hard disk?

Because hard disks have different performance characteristics than RAM.

With hard disks, seeking is extremely slow. Sequential reads are much faster than random-access reads. In other words, it's much faster to read data that is stored consecutively than to store data that's scattered all around the disk. Therefore, there are benefits to making sure your files are contiguous, as much as possible.

RAM doesn't have the same property. With RAM, there is no penalty for "seeking". You can pick any page and read from it, and the cost will be the same, no matter where the page is located. For instance, reading page X and then page Y will have the same cost regardless of whether X and Y are adjacent or not.

So, you end up with different algorithms that are optimized for hardware with different performance characteristics.

Why do hard disks have this strange property? Because they are based on a rotating piece of iron. If you read block X on the hard disk, and next want to read block Y, but Y is on the other side of the platter, then you'll have to wait for the platter to finish rotating far enough for Y to be under the read head. That takes time. RAM doesn't have this property.

Interestingly, the differences are becoming less these days. Today, SSD (solid state storage devices, based on Flash storage) are becoming a popular replacement for hard disks. SSD's have their own performance characteristics, but they're more like RAM than like magnetic hard disks. This means that the filesystem optimizations you'd do for a SSD-oriented filesystem are different from the ones you'd do for a hard-drive-oriented filesystem. Many of today's filesystems were designed decades ago when magnetic hard disks were dominant, and optimize for the performance characteristics of magnetic hard disks.

Why not harden software by deliberately leaving space between buffers?

You are implicitly proposing a scheme for making software more robust against out-of-bounds errors and buffer overruns: leave plenty of unallocated space between each pair of buffers allocated on the heap.

That's not a bad idea. It's been proposed before and studied in considerable depth. It does add some robustness against bugs. It can also make buffer overrun attacks harder, especially if you randomize the location of all heap buffers. It's also relatively easy to deploy in a way that is compatible with legacy software. So it does have some quite attractive advantages.

However, it also has some disadvantages. It imposes some performance overhead -- not a huge amount, but enough to be a bit painful. Why does it impose performance overhead? Largely because it reduces spatial locality. Consider two 16-byte allocations. Current allocators try to pack them together into a single page. In your scheme, we'd have to put each allocation onto its own page. That means we have a lot more pages, which means that we get a lower TLB hit rate.

There are different variants on this scheme, with different performance implications, but they all run up against the challenge: in exchange for the robustness and security benefits, there is some non-zero performance overhead. So that's one reason why people might not adopt it.

The other big reason is: we're using platforms and allocators that were designed decades ago. At the time, security wasn't as critical as it is today, so this sounded like a pretty unattractive proposal: I get to implement something more complicated and fiddly, and it'll make my entire system slower? No thanks.

Today given the magnitude of security problems we're facing, there's gradually increasing interest in these alternatives. But they still face an uphill battle, because of the non-zero performance implications.

To learn more about academic research on this subject, read research papers on the Diehard, Dieharder, and Archipelago systems. They discuss the design in a very accessible way and measure the performance and other costs of such a scheme. If you're still intrigued, you can explore the literature where other researchers have explored other points in the design space to understand their implications.

Bottom line: you're not the first to think of this, and it is a pretty attractive idea, but it also comes with some significant costs.

$\endgroup$
  • $\begingroup$ The reason I think it could be useful is for buffer expansion & corruption detection, not to reduce RAM seeking. Also, I'm not talking about physical ram, I'm talking about virtual ram, so it can be sequential or not physically, as you say, it's irrelevant. This is a realloc optimization to make it drastically or even never needed to be moved, only resized due to the amount of virtual ram address space. $\endgroup$ – JavaProphet Jul 23 '16 at 3:47
  • $\begingroup$ @JavaProphet, OK, that's a different question -- one that has nothing to do with filesystems or ext4. Your opening sentence made me think you were asking about something else. Sorry. I suggest you read the papers "Diehard", "Dieharder", & "Archipelago" from the research literature (e.g., by Berger et al). I suspect you'll find the answer there. In general, the first answer to "why don't we do (this-extra-thing-for-security)?" is usually going to be "it's more complicated and slower, and when systems were designed security was less important", which probably isn't what you're looking for. $\endgroup$ – D.W. Jul 23 '16 at 4:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.