LWN: Comments on "Solid-state storage devices and the block layer"

bogus random entropy sources

cladisch — Tue, 07 Feb 2012 07:50:44 +0000

The Windows 8 Hardware Certification Requirements demand that "Connected Standby"-capable device (i.e., mobile ones) have encryption acceleration and a RNG.

> Business Justification:
> Core cryptographic functions are used in Windows to provide platform integrity as well as protection of user data.
(note the priorities)

In completely unrelated news, all recent AMD and Intel processors support AES-NI, and Intel has announced that Ivy Bridge processors will have a RNG.

bogus random entropy sources

dlang — Mon, 06 Feb 2012 21:40:11 +0000

some chips do have high quality random number generators built in.

bogus random entropy sources

tconnors — Mon, 06 Feb 2012 21:33:17 +0000

> Modern CPUs have accelerators for all sorts of things as standard equipment. Why not random numbers? We spend countless millions of transistors on ever larger caches and datapaths. Surely they could spare a few for a really high quality true random number generator.

Because random number generators are only used for cryptography, and only terrorists use cryptography. Are you a terrorist?

Solid-state storage devices and the block layer

eds — Fri, 22 Oct 2010 22:04:23 +0000

There are many good reasons to treat NAND flash storage more like disk than like DRAM.

1. Addressing: DRAM is byte/word addressable; NAND flash is not. NAND flash pages are currently 4KB in size and must be read/written
2. Flash management: flash sucks. It has long erase times, needs wear-leveling, needs lots of ECC and redundancy to be reliable. Dealing with flash requires a lot of careful management that nobody's going to want on a DRAM-like path.
3. Speed: flash is a lot faster than disk. But it's still a lot slower than DRAM (a write to a busy NAND part may have to wait up to 1ms).
4. Size: it's very expensive to try to address a terabyte of DRAM. 64-bit CPUs don't actually implement a full 64-bit address space. It's much cheaper to just address huge storage devices in blocks, like a disk.

If in a few more years phase-change memory becomes big and cheap enough to give NAND flash a run for its money, then it may be time to start treating nonvolatile memory sort of like DRAM. But that day isn't quite here yet.

Solid-state storage devices and the block layer

jmy3056 — Fri, 15 Oct 2010 17:42:12 +0000

I think the analogy presented misses the mark. Instead of equating block IO with Network improvements consider this.

Media that stores electronic information that used to spin but now doesn't is a closer parallel with RAM. Optimzations for "disk" IO need to follow a similar path as OS/kernels when dealing with RAM.

application impact

Wol — Thu, 14 Oct 2010 19:29:43 +0000

That's fine until they're on a system like mine ...

Three slots, max capacity 256Mb per slot, three 256Mb chips in the machine.

"That's no problem, they can just buy a new machine ..."

Cheers,
Wol

Getting more entropy

man_ls — Sun, 10 Oct 2010 21:56:14 +0000

I guess that the problem is to prove that an attacker cannot influence the timers so that the result is predictable. For example a guy on a different VM doing odd things with the same CPU. As it is hard to prove a negative statement of this kind, then people may tend to distrust such a source of entropy, even if it sounds really interesting.

Getting more entropy

kleptog — Sun, 10 Oct 2010 11:55:01 +0000

A while back just for the fun of it I wrote a kernel driver whose goal was to extract entropy from the timer interrupt. After all, if anything is predictable, then it'd have to be the timer interrupt.

The point is that while the interrupt is predictable, between the time that the interrupt fires and the driver finally gets run you have cache misses at various levels, PCI bus transfers, DRAM refresh cycles and even just hyperthreading making things very unpredictable. Conclusion: if there's predictability here, I couldn't find it (there's a toolkit for estimating randomness, it concluded that the output was indistinguishable from real random data).

The basic idea was to just use the last few bits of the cycle counter, don't worry about the high order bits. The last bit was enough, but even taking the last four bits didn't show any patterns. It might be worth making such a driver for the purpose of giving otherwise entropy starved machines something to work with. I imagine within VMs the cycle counter becomes even more variable, due to contention with things outside the VM.

Solid-state storage devices and the block layer

jzbiciak — Sat, 09 Oct 2010 15:03:13 +0000

Note: I'm not an expert. Please do not mistake me for one. :-) Here are my observations, though, along with things I've read elsewhere.

Flash requires wear leveling in order to maximize its life. For the greatest effect, you want to wear level across the entire device, which means picking up and moving otherwise quiescent data so that each sector sees approximately the same number of erasures. That's one aspect.

Another aspect is that erase blocks are generally much larger than write sectors. So, when you do erase, you end up erasing quite a lot. Furthermore erasure is about an order of magnitude slower than writing, and writing is about an order of magnitude slower than reading. For a random flash device whose data sheet I just pulled up, a random read takes 25us, page program takes 300us, and block erase takes 2ms. Pages are 2K bytes, whereas erase blocks are 128K bytes.

(Warning: This is where I get speculative!) And finally, if you have multiple flash devices (or multiple independent zones on the same flash device), you can take advantage of that fact and the fact that "seeks are free" by redirecting writes to idle flash units if others are busy. That's probably the most interesting area to explore algorithmically, IMO. Given that an erase operation can take a device out of commission for 2ms, picking which device to start an erase operation on and when to do it can have a pretty big impact on performance. If you can do background erase on idle devices, for example, then you can hide the cost.

Solid-state storage devices and the block layer

dlang — Sat, 09 Oct 2010 14:55:09 +0000

the issue is that you have to erase large chunks (on the order of 128K bytes), if you are then writing in small chunks (say the 512 byte sectors that are the default, or even the 4K byte filesystem blocks) you can't just erase just before writing.

you also have the problem that erasing takes a significant amount of time and power to accomplish, so you don't want to wait until you need to erase to do so and you don't want to erase when you don't need to and are on battery

Solid-state storage devices and the block layer

joern — Sat, 09 Oct 2010 14:10:41 +0000

> Flash does require you to think about how you pool your free sectors, though, and how you schedule writing versus erasing.

Intriguing. Can you elaborate a bit? What difference does it make vs. the naïve approach of erasing before writing?

Solid-state storage devices: most I/O patterns

giraffedata — Sat, 09 Oct 2010 00:00:03 +0000

While workloads will vary, Jens says, most I/O patterns are dominated by random I/O and relatively small requests.

There are so many ways to count "most" that this fact is pretty useless. Jens should just say, "some important I/O patterns are ...," which is reason enough to do this work.

I see a lot of thought wasted prioritizing things based on arbitrary "mosts": Most I/Os are reads, most files are under 4K, most computers are personal workstations.

Solid-state storage devices and the block layer

giraffedata — Fri, 08 Oct 2010 23:48:03 +0000

Probably the main reason why such an unfortunate IOPS jump has been forced in networking is backward compatibility.
...
In comparison, the need for backward compatibility in storage is basically inexistent.

Well, the the whole reason SSDs exist is backward compatibility with rotating media, and it does slow things down considerably. If not for backward compatibility, we wouldn't use SCSI or even Linux block devices to access solid state storage. Write amplification by read-modify-write wouldn't be a problem if the device weren't trying to emulate a 512-byte-sectored disk drive.

Existence of SSDs tells me people aren't willing to replace the entire system at once -- they want to replace just the disk drives.

Not knowing the network issues, though, I can believe that backward compatibilty hinders performance less in storage than for ethernet.

bogus random entropy sources

BenHutchings — Thu, 07 Oct 2010 14:34:25 +0000

Most network controllers now implement interrupt moderation (deferring interrupts so that multiple packets can be handled at once). With a high enough packet rate, they will interrupt at regular and predictable intervals.

bogus random entropy sources

intgr — Thu, 07 Oct 2010 12:48:30 +0000

For virtual machines you already have a paravirtual RNG device called 'virtio-rng' (CONFIG_HW_RANDOM_VIRTIO).

But in general, virtual machine disk I/O still reaches a physical disk sooner or later, so entropy can be successfully gathered from interrupt timings. In some virtualization scenarios, you wouldn't want the VM to access host-CPU-specific features anyway.

Solid-state storage devices and the block layer

nix — Thu, 07 Oct 2010 12:38:23 +0000

NAND flash has a notion of "sequential page read" versus "random page read". If you're truly reading random bytes a'la DRAM w/out cache, you'll see noticeably slower performance if the two reads are in different pages.

That sounds just like normal RAM: if you don't have to specify the row *and* column, you save on one CAS/RAS select cycle. Of course this is hidden behind the MMU and CPU cache management code and so on, so we don't often notice it, but it is there.

bogus random entropy sources

nix — Thu, 07 Oct 2010 12:28:52 +0000

From all accounts I've read, the entropy of the numbers derived from the C3's RNG hardware sucks rather badly, probably because there are so many sources of regular noise in a CPU that it's hard to stop some of them leaking in. The figures I've heard are *well* below 0.75, more like 0.4 if you're lucky. And IIRC the C3 doesn't bother to validate them either (certainly from the description in the whitepaper they don't), and because the pair of oscillators comprise a single system, if it breaks down or becomes coupled to something external you *also* cannot tell.

bogus random entropy sources

nix — Thu, 07 Oct 2010 12:24:09 +0000

"Diskless embedded systems" of course includes "all virtual machines". So there are a lot of them.

Solid-state storage devices and the block layer

eds — Wed, 06 Oct 2010 22:05:10 +0000

Good article.

At the extreme high end of PCIe SSDs, a system trying to do lots of small (4k) reads with high parallelism will be limited by having any queue locking at all. Running without a request queue remains an attractive option for these devices.

Another future improvement to watch out for is MSI-X interrupts. With MSI-X, it is possible to statically assign an interrupt to a single CPU core in such a way that an I/O retirement could interrupt the originating CPU directly; over about 600K IOPS it becomes important to spread out the interrupt/retirement workload as much as possible.

bogus random entropy sources

paulj — Wed, 06 Oct 2010 19:34:06 +0000

Hehe, so shred was using entropy collected from the disk controllers, collected from shred writing to disks..

bogus random entropy sources

drag — Wed, 06 Oct 2010 17:01:33 +0000

I know that I have had problems with ssh hanging on new nodes on xen due lack of entropy. But I think this is no longer a problem.

bogus random entropy sources

jzbiciak — Wed, 06 Oct 2010 13:56:45 +0000

Probably because they didn't have a time machine. ;-) The document you reference was written this year. The white paper I reference was written in 2003. And if you meant Rev 1, that didn't come out until 2008.

Maybe you meant the original 800-22? That one came out in 2001.

(Dates came from here.)

bogus random entropy sources

intgr — Wed, 06 Oct 2010 11:27:47 +0000

> without getting something more basic and generic like random numbers on there too.

The solution has always been obvious to cryptographers. Use a solid cryptographical pseudorandom RNG; as long as there is _some_ truly random data in its input -- 128 or so bits worth -- the output will always be irreversible. As long as this randomness exists, it doesn't matter that the attacker can predict all other input.

In fact, hardware RNGs should _never_ be used directly, because there may be manufacturing flaws or deliberate sabotage. And unlike deterministic algorithms like AES, non-deterministic hardware RNG sources are almost impossible to verify completely. Also it's really quite easy to replace the hw RNG with a deterministic PRNG that passes all randomness tests, yet whose output is entirely predictable to its designer.

So at most, the hw RNG is just one of several randomness sources on any system. As such cryptographers in general don't consider it worthwhile -- only on diskless embedded systems where there really aren't any entropy sources.

Unfortunately /dev/random is a poor legacy choice in Linux that goes against this concept.

application impact

dlang — Wed, 06 Oct 2010 11:04:48 +0000

it depends on what you are measureing

in terms of size, drives have grown at least 1000x

in terms of sequential I/O speeds they have improved drastically (I don't think quite 1000x, but probably well over 100x, so I think it's in the ballpark)

in terms of seek time, they've barely improved 10x or so

this is ignoring things like SSDs, high-end raid controllers (with battery backed NVRAM caches) and so on which distort performance numbers upwards.

byt yes, the performance difference between the CPU registers and disk speeds is being stretched over time.

jut the difference in speed between the registers and ram is getting stretched to the point where people are seriously talking that it may be a good idea to start thinking of ram as a block device, accessed in blocks of 128-256 bytes (the cache line size for the CPU), right now the CPU hides this from you by 'transparently' moving the blocks in and out of the cache of the various processors for you so that if you choose to you can ignore this.

but when you are really after performance, a high end system starts looking very strange. You have several sets of processors that share a small amount of high-speed storage (L2/L3 cache) and have larger amount of lower speed storage (the memory directly connected to that CPU), plus a network to access the lower speed storage connected to other CPUs. Then you have a lower speed network to talk to the southbridge chipset to interact with the outside world (things like you monitor/keyboard/disk drives, PCI-e cards, etc).

This is a rough description of NUMA and the types of things that you can run into on large multi-socket systems, but the effect starts showing up on surprisingly small systems (which is why per-cpu variables and such things are used so frequently)

application impact

marcH — Wed, 06 Oct 2010 09:23:31 +0000

I doubt that hard drive performance (as considered in this article) has increased 1000x. Has it? The memory hierarchy looks more and more stretched.

(Here I am ignoring SSDs, still too new to be part of The History)

bogus random entropy sources

pcampe — Wed, 06 Oct 2010 08:40:18 +0000

I don't understand why they didn't follow the guidelines in NIST Standard 800-22 (rev 1a), "A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications".

bogus random entropy sources

jzbiciak — Wed, 06 Oct 2010 03:51:19 +0000

I linked this whitepaper above on the technique VIA used on its C3. They used multiple free-running oscillators to gather entropy. The resulting output varies in quality, from 0.75 to 0.99 bits of entropy per output bit, depending on the decimation factor used and whether or not you enable von Neumann whitening.

Given that it generates entropy in the megabits/second range, this is several orders better than you can get from hard disk seeks and user keystrokes, even if you have to throw most of the numbers away. And, given the high apparent entropy of the raw bits, you don't really need to throw many away at all.

bogus random entropy sources

jzbiciak — Wed, 06 Oct 2010 03:47:30 +0000

Well, /dev/urandom doesn't block when the kernel entropy pool runs out. The hardware crypto acceleration may've been getting used, but that's orthogonal to the question of gathering entropy.

bogus random entropy sources

PaulWay — Wed, 06 Oct 2010 03:36:54 +0000

Purely an anecdote, but the other day I had the occasion to use shred to shred two disks at once. The machine was a modern Intel Core Quad system, and the disks were writing at 60MBytes/sec with 3% CPU load. Since modern shred just writes a number of layers of pure random data from /dev/urandom, I have to assume that there was either hardware crypto or randomness generation going on there. Who knew?!

Have fun,

Paul

application impact

dlang — Wed, 06 Oct 2010 01:23:49 +0000

the problem is that system resources have increased by 1000x (or close to it) and people trying to do very similar work find themselves in almost the same situation.

yes we are doing more with our systems, but nowhere near that much more.

application impact

mpr22 — Wed, 06 Oct 2010 00:16:13 +0000

Eight Megabytes And Constantly Swapping. This is not a new phenomenon.

Solid-state storage devices and the block layer

marcH — Tue, 05 Oct 2010 23:30:15 +0000

> If it's to be believed, IPv6 transition is quite far from "smooth".

Yes but it would have been much worse (read: impossible) if IPv6 deployment ever required substantial changes to IPv4.

This is an interesting article. Except they are wrong when they pretend it is easy to break backward-compatibility with Ethernet or TCP. It is not easy but only "less impossible" than breaking IPv4 backward compatibility.

Note: the focus of the article is obviously neither on Ethernet nor on TCP.

application impact

zlynx — Tue, 05 Oct 2010 22:29:01 +0000

I sure hope not.

GTK applications' current "best practice" of "ignore the RAM use, they can buy more" has already destroyed the usefulness of old hardware with a modern Linux software stack.

bogus random entropy sources

nowster — Tue, 05 Oct 2010 21:58:55 +0000

> I don't understand why more processors don't include a proper hardware random number generator.

It's actually a hard problem to provide a cheap reliable hardware random number generator. If you look at the effort that a device like Simtec's Entropy Key takes to ensure that each chunk of randomness it delivers is truly random, you'll see why a random number generator is not something that a CPU designer should drop on a spare corner of a CPU die last thing on a Friday afternoon. Semiconductor junction noise generators can be affected by environmental influences: an RNG on a CPU die running hot might have a bias compared with the same one when the CPU is idle and cooler.

iSCSI, Solid-state storage devices and the block layer

jhhaller — Tue, 05 Oct 2010 21:17:17 +0000

Is using iSCSI to use Solid State disks mounted on a file server part of the testing and improvement plan? I can imagine this stresses both worlds, namely network interrupt steering along with block devices, all interacting in less than obvious ways.

Solid-state storage devices and the block layer

jzbiciak — Tue, 05 Oct 2010 20:38:07 +0000

You can do random writes to random empty sectors. Again, that's nothing like how a hard disk works. I'm still strenuously disagreeing with your earlier statement that flash's properties make it more like a disk than like RAM. It's really an entirely different beast worthy of separate consideration, which is why I think wrapping it up in an SSD limits its potential.

With flash, you need entirely new strategies that apply neither to disks nor RAM to get the full benefit from the technology. Much of the effort spent on disks revolves (no pun intended) around eliminating seeks. No such effort is required with RAM or with flash. Flash does require you to think about how you pool your free sectors, though, and how you schedule writing versus erasing. I won't deny that. Rather, I say it only further invalidates your original conjecture that it makes flash more like disks. (I will agree it makes it less like RAM though.)

Because seeks are "free", I could totally see load balancing algorithms of the form "write this block to the youngest free sector on the first available flash device", so that a new write doesn't get held up by devices busy with block erases. That looks nothing like what you'd want to do with a disk. It takes advantage of the "free seek" property of the flash while helping to hide the block erase penalty it imposes. Neither property is a property of a disk drive. Of course, neither property is a property of RAM, either.

Am I splitting hairs over semantics here? Let me step back and summarize, and see if you agree: Raw flash's random access capability and relatively low access time can make it much more like RAM than disk, especially in terms of bandwidth and latency. Raw flash's limitations on writes, however, require the OS to have flash-specific write strategies. They prevent the OS from treating flash identically to RAM, and will require careful thought to be handled correctly. This is similar to how we had to put careful thought into disk scheduling algorithms, even if flash requires entirely different algorithms to address its unique properties.

Solid-state storage devices and the block layer

dlang — Tue, 05 Oct 2010 19:42:26 +0000

flash allows for random access reads, but is much more limited for writes.

Solid-state storage devices and the block layer

jzbiciak — Tue, 05 Oct 2010 19:27:28 +0000

It certainly is random access. I can generally send a command for address X followed by a command for address Y to the same chip, where the response time is not a function of the distance between X and Y, except when they overlap. Instead, the performance is most strongly determined by what commands I sent[*]. Reads are much faster than writes, and both are much, much faster than sector erase.

The opposite is generally true of disks. There, the cost of an operation is more strongly determined by whether it triggered a seek (and how far the seek went) than if the operation was a read or a write. Both reads and writes require getting the head to a particular position on the platter, ignoring any cache that might be built into the drive. Also, under normal operation, spinning-rust drives don't really have an analog to "sector erase." (Yes, there's the old "low-level format" commands, but those aren't generally used during normal filesystem operation.)

[*] Ok, so that's not 100% true, but essentially true in the current context. NAND flash has a notion of "sequential page read" versus "random page read". If you're truly reading random bytes a'la DRAM w/out cache, you'll see noticeably slower performance if the two reads are in different pages. But, if you're doing block transfers, such as 512-byte sector reads, you're reading the whole page. Hopping between any two sectors always costs about the same. Here, read a data sheet! For this particular flash, a random sector read is 10us, sector write is 250us, and page erase is 2ms. The whole page-open/page-close architecture makes it look much more like modern SDRAM than disk.

bogus random entropy sources

jzbiciak — Tue, 05 Oct 2010 19:10:45 +0000

VIA's approach on the C3 doesn't sound too unwieldy. This white paper analyzing the generator's output makes for an informative read. The punch line is that it looks like a pretty reasonable source of entropy as long as you do appropriate post processing. The random numbers it generates aren't caveat free, but they're heckuva lot better than disk seeks and keypresses.

bogus random entropy sources

patrick_g — Tue, 05 Oct 2010 19:01:48 +0000

>>> I don't understand why more processors don't include a proper hardware random number generator. It's a classic case of something that is significantly easier to do in hardware, I'd think.

I think Intel will is working on this.
See these link : http://www.technologyreview.com/computing/25670/