8 ms·

Kernel – Fix cluster_write() inefficiency

84 points by protomyth 10y ago

microcolonel 10y ago
Always wondered where the bandwidth was going when I was using HAMMER. Had to use UFS when testing last time.
re 10y ago
Looks like HAMMER is DragonFlyBSD's filesystem, for those (like me) who may be unfamiliar with the distro: http://www.dragonflybsd.org/hammer/ http://www.dragonflybsd.org/hammer/ Previous discussion about the filesystem vs. ZFS: https://news.ycombinator.com/item?id=8829194 https://news.ycombinator.com/item?id=8829194
- walkingolof 10y ago
  Not really fair to call it a distro, you get the wrong impression, its was forked of FreeBSD 2002 or 2003
  - roninb 10y ago
    Distro is synonymous with OS at this point. No one is using it as a derogatory term for OSes that aren't different enough to give them the denotation of "OS". That said, you're going to have to come up with an argument stronger than "this was forked ages ago" to suggest Dragonfly and FreeBSD are different enough to warrant thought. Ubuntu forked before 2004 and you don't see anyone being called out for comparing it to Debian.
    - rincebrain 10y ago
      DFBSD has substantial kernel differences from FreeBSD (IIRC the original reason for the fork was that the author disagreed about how to implement multiprocessor scheduling and went off to do it his way), such that the diff between the FBSD tree and the DFBSD tree would be enormous at this point. Drivers sometimes make their way between the two, I believe, but it isn't just a copy-paste operation. Ubuntu and Debian's kernels, on the other hand, are kept as itemized patchsets against the same kernel, and it would be hard (but probably not impossible) to find drivers that build+work on a Debian kernel and break on an Ubuntu kernel of similar age.
    - laumars 10y ago
      > Distro is synonymous with OS at this point. Possibly to the layman but the term "distro" (short for "distribution") deliberately exists to differentiate between different OS's and different distributions of the same OS but with a different software stack and default configurations. While you do sometimes get differences between the Linuxes in terms of init daemons and slightly patched kernels etc, they are all generally GNU/Linux - ie generally share the same common Linux OS fundamentals (eg GNU coreutils). There will be exceptions to this rule (isn't there always?!) but we're talking about the common desktop / server platforms people automatically talk about when discussing "Linux". However many of the BSDs are developed in insolation. While they may have a shared heritage, the kernels have matured into something quite different from one another. Often the core utilities and init daemons et al can vary noticeably as well. So in essence, FreeBSD and Dragonfly are different but similar OSs, whereas Linux distributions are the same OS but differently configured. This is why we make the distinction between "distro" and "OS".
      - _delirium 10y ago
        I've been experimenting with Debian/kFreeBSD lately, and one funny aspect it's had is making me realize that the kernel is not really all that important to the userland experience, at least for what I do. It still feels like Debian, even though they swapped out the Linux kernel for the FreeBSD kernel. That's one reason I think of Debian as an OS, rather than a Linux distro. Debian itself then has several distros, such as Debian/Linux and Debian/kFreeBSD.
        gpvos 10y ago
        It might be more useful to see distro as orthogonal to OS. Is Debian/Darwin a thing yet? :)
        laumars 10y ago
        I get your point, but aside the package manager and associated tools, most of what you've described are GNU packages / cross platform user land. ie stuff that even in the most limited sense was never Debian specific to begin with; but often was designed to run on most Unix-like platforms anyway. Because of this I've read some people describe kFreeBSD as GNU/kFreeBSD (ie GNU user land with the FreeBSD kernel) and I think that makes some sense if you're following the GNU/Linux naming convention (which I think makes sense in the context of this discussion because it also takes the Hurd kernel into account - GNU/Hurd). But this is one of those edge cases I was thinking of when I talked about exceptions to the rule in my grandparent post. As for whether it's classified as a separate OS from Debian (Linux) or FreeBSD - there's definitely some room for interpretation so I'll hold off from passing my own personal judgement :) Talking about rule exceptions, another good example would be Android. Largely the same kernel as GNU/Linux and some of the user land too but equally it's a very different platform to "desktop / server Linux"
    - feld 10y ago
      An OS is a kernel and userland developed together in its entirety. All the code shipped is maintained by a single responsible entity: an open source team or a company. External code is imported into the source tree and treated as if it is owned by the team. Any patches required for it to integrate cleanly are the responsibility of the OS maintainers. A distro is a Linux kernel and a collection of open source software, typically GNU, which fulfills the needs of the userland environment. The distro maintainers are responsible for packaging and distribution. They are not responsible for maintaining the kernel or any of the userland software unless it was internally developed such as a custom installer or various glue code, maintenance scripts, etc. They do not own the libc, the kernel, the shell, any drivers, responsibility for writing security patches, or bug fixes for any code they did not originally write, etc. The distro volunteers or employees of the company in charge of producing the distro may be involved in kernel or other open source softeare development, but it is not required. This may be an unpopular statement, but a Linux distro is not an OS. It is a collection of open source software that tries to be compatible with all of its components. Subject matter experts of all components are usually not involved in its creation. Instead they exist spread out across the entire Linux distro ecosystem. Does Arch Linux have an expert in the virtual memory subsystem of the kernels they ship? Does Gentoo have an expert in the kernel random code? Does Debian have an expert in the glibc codebase? Does Ubuntu have an expert in the bootloader? Does Mint Linux have an expert in the BASH code they ship? I can say with confidence that Suse and Redhat employ experts of many areas of the kernel, glibc, systemd, filesystems, and other components, but not everything. Does FreeBSD/Dragonfly/OpenBSD have an expert or designated owner of the filesystems they ship? Bootloaders? Libc? Kernel timekeeping code? Random? Crypto? VFS? Network stack? NIC drivers? CPU schedulers? Shells and userland utilities? Yes they do. They're OSes, entirely maintained in-project. Just like Windows, OSX, Solaris, etc. OpenBSD is most aggressive here, but unmaintained code usually means nobody is using it and it will be removed. Everything has an owner and is constantly being looked after. In the BSD world it would not be common for a major component to exist long term without an SME joining the project and maintaining it or replacing it. BSDs are OSes, and are mostly independent. You cannot easily port kernel code between them because they have diverged significantly.
      - elros 10y ago
        > An OS is a kernel and userland developed together in its entirety. [citation needed]? How is a Linux distro not an OS? Isn't it the Operating System on whatever machine it's running? If I run Ubuntu or Arch, what OS am I using?
- ksec 10y ago
  That was against HAMMER 1, which is completely different to HAMMER 2.
jemfinch 10y ago
Reading the diff, I'm neither surprised that this bug existed nor will I be surprised when similar bugs arise. There must be a more readable to write even low-level code like this.
- koverstreet 10y ago
  Yes, there is. That code needs iterators.
  - yoklov 10y ago
    but most of that code isn't iterating. the only parts in that function i see that are iterating ([0] and the similar loop below it) seems straightforward enough to me. i don't see how they would help here unless i don't know what you mean by iterators (assuming c++-style iterators or similar). [0]: http://gitweb.dragonflybsd.org/dragonfly.git/blob/cf297f2cccd7fd102041ebf174af66a31a5ef5ce:/sys/kern/vfs_cluster.c#l1294 http://gitweb.dragonflybsd.org/dragonfly.git/blob/cf297f2ccc...
- yoklov 10y ago
  honestly, i think it's hard to say this generally without more context into the code. imo nothing there looks too egregious (or at least not abnormally so) for very low level code.
remy_luisant 10y ago
Couldn't they dump out the list of all individual write commands sent to the disk and have seen that the writes are in a suboptimal pattern? This would have been one of the first things I would have done when testing a file system of any kind: Make sure the thing writes what I want to be written and in the way I want it to be written.
- forgottenacc57 10y ago
  Many problems have obvious solutions in hindsight.
- josh64 10y ago
  Isn't NCQ meant to do this? I mean reorder the write commands into an optimal order.
- koverstreet 10y ago
  You don't even need to do anything that hard. All you need to is run basic benchmarks and compare the results to what other filesystems can do, and when yours is about half as fast that should make you go "huh"...
  - rurban 10y ago
    Hammer is twice as fast, not half. So huh
    - sleepychu 10y ago
      So it'll now be 4x?
      - rurban 10y ago
        We need benchmarks, and this is the old version only.
- cat199 10y ago
  People write bugs occasionally. You're talking about the person who spent months tracking down what everyone else thought was a code or compiler bug but actually proved was a subtle CPU bug requiring vendor errata releases, and further, who wrote this log-structured, snapshottable, syncable low-memory using, real-world filesystem from scratch for the highly parallel operating system he has been rearchitecting for over 10 years now. There are consistent status update posts outlining the on disk filesystem structure, as well as its relation to the virtual memory subsystem and the in-kernel parallelism feeding IO writes, as well as constant code commits implementing these things, so I'd reserve the need to back-seat drive here unless I could back it up with a comparable body of work. http://www.theregister.co.uk/2012/03/07/amd_opteron_bug_dragonfly/ http://www.theregister.co.uk/2012/03/07/amd_opteron_bug_drag...
josteink 10y ago
So if I'm reading this patch correctly it's now writing things in blocks instead of as single bytes? Is that it? And, well, yes. Ofcourse that does wonder's for throughput. And I would certainly hope that someone who writes a file-system knows that. Edit: Re-reading the patch it seems like what's being done here is taking a (failed) at attempt at writing in blocks and actually making it write in proper block-sizes. Yay C, I guess.
- TheDong 10y ago
  Wow, somehow you managed to read the patch without reading the commit message that explains what actually changed. No, you didn't read it correctly.
  - josteink 10y ago
    Well yes actually. The fault is completely on me. But in my defence, the code and diff is all colourful and highlighted... While the patch description is "hiding" very subtly in plain sight at the top. When someone is new to any kind of system, their eyes will follow what attracts their attention. I didn't even notice there was a commit message there until you told me. Some minor UI tweaks could probably improve that page greatly :)
    - pmontra 10y ago
      Yes, they should increase the font size of the log section. It's as simple as .log { font-size: large; } using their CSS class and their conventions for font sizes.
    - kzrdude 10y ago
      It's amazing how good we are at filtering information at all levels. I agree with you that the design of the page plays a large part. GitHub probably had more time & reason to optimize this.
HugoDaniel 10y ago
How often does a sequential write happen in an SSD ?
- pmontra 10y ago
  As often as it happens with HDD, I think. Anyway, with my SSD: I unzipped a 300 MB Raspbian lite zip into a 1.3 GB image yesterday and extracted parts from a 8 GB video with mmpeg last weekend. I expect all of them to be sequential given enough free space on the SDD (same for HDDs.) I also work with docker and vagrant and building those images at half speed can't be good.
- digikata 10y ago
  Almost always if one wants to optimize...
Upvoter33 10y ago
wow, this is an embarrassing bug. To say it doubles bandwidth makes it sound like an optimization, when in fact it is just (finally) doing what you think it should be doing. Yikes- how long was this doing this and no one noticed?
- kzrdude 10y ago
  Data loss and corruption is always a lot more embarrassing. Did they have tests that ensure correctness (in data) of the slow version? Then they were already delivering on quality of the file system.

84 points by protomyth 10y ago

Always wondered where the bandwidth was going when I was using HAMMER. Had to use UFS when testing last time.

re 10y ago

Looks like HAMMER is DragonFlyBSD's filesystem, for those (like me) who may be unfamiliar with the distro: http://www.dragonflybsd.org/hammer/ http://www.dragonflybsd.org/hammer/ Previous discussion about the filesystem vs. ZFS: https://news.ycombinator.com/item?id=8829194 https://news.ycombinator.com/item?id=8829194

walkingolof 10y ago
Not really fair to call it a distro, you get the wrong impression, its was forked of FreeBSD 2002 or 2003
- roninb 10y ago
  Distro is synonymous with OS at this point. No one is using it as a derogatory term for OSes that aren't different enough to give them the denotation of "OS". That said, you're going to have to come up with an argument stronger than "this was forked ages ago" to suggest Dragonfly and FreeBSD are different enough to warrant thought. Ubuntu forked before 2004 and you don't see anyone being called out for comparing it to Debian.
  - rincebrain 10y ago
    DFBSD has substantial kernel differences from FreeBSD (IIRC the original reason for the fork was that the author disagreed about how to implement multiprocessor scheduling and went off to do it his way), such that the diff between the FBSD tree and the DFBSD tree would be enormous at this point. Drivers sometimes make their way between the two, I believe, but it isn't just a copy-paste operation. Ubuntu and Debian's kernels, on the other hand, are kept as itemized patchsets against the same kernel, and it would be hard (but probably not impossible) to find drivers that build+work on a Debian kernel and break on an Ubuntu kernel of similar age.
  - laumars 10y ago
    > Distro is synonymous with OS at this point. Possibly to the layman but the term "distro" (short for "distribution") deliberately exists to differentiate between different OS's and different distributions of the same OS but with a different software stack and default configurations. While you do sometimes get differences between the Linuxes in terms of init daemons and slightly patched kernels etc, they are all generally GNU/Linux - ie generally share the same common Linux OS fundamentals (eg GNU coreutils). There will be exceptions to this rule (isn't there always?!) but we're talking about the common desktop / server platforms people automatically talk about when discussing "Linux". However many of the BSDs are developed in insolation. While they may have a shared heritage, the kernels have matured into something quite different from one another. Often the core utilities and init daemons et al can vary noticeably as well. So in essence, FreeBSD and Dragonfly are different but similar OSs, whereas Linux distributions are the same OS but differently configured. This is why we make the distinction between "distro" and "OS".
    - _delirium 10y ago
      I've been experimenting with Debian/kFreeBSD lately, and one funny aspect it's had is making me realize that the kernel is not really all that important to the userland experience, at least for what I do. It still feels like Debian, even though they swapped out the Linux kernel for the FreeBSD kernel. That's one reason I think of Debian as an OS, rather than a Linux distro. Debian itself then has several distros, such as Debian/Linux and Debian/kFreeBSD.
      - gpvos 10y ago
        It might be more useful to see distro as orthogonal to OS. Is Debian/Darwin a thing yet? :)
      - laumars 10y ago
        I get your point, but aside the package manager and associated tools, most of what you've described are GNU packages / cross platform user land. ie stuff that even in the most limited sense was never Debian specific to begin with; but often was designed to run on most Unix-like platforms anyway. Because of this I've read some people describe kFreeBSD as GNU/kFreeBSD (ie GNU user land with the FreeBSD kernel) and I think that makes some sense if you're following the GNU/Linux naming convention (which I think makes sense in the context of this discussion because it also takes the Hurd kernel into account - GNU/Hurd). But this is one of those edge cases I was thinking of when I talked about exceptions to the rule in my grandparent post. As for whether it's classified as a separate OS from Debian (Linux) or FreeBSD - there's definitely some room for interpretation so I'll hold off from passing my own personal judgement :) Talking about rule exceptions, another good example would be Android. Largely the same kernel as GNU/Linux and some of the user land too but equally it's a very different platform to "desktop / server Linux"
  - feld 10y ago
    An OS is a kernel and userland developed together in its entirety. All the code shipped is maintained by a single responsible entity: an open source team or a company. External code is imported into the source tree and treated as if it is owned by the team. Any patches required for it to integrate cleanly are the responsibility of the OS maintainers. A distro is a Linux kernel and a collection of open source software, typically GNU, which fulfills the needs of the userland environment. The distro maintainers are responsible for packaging and distribution. They are not responsible for maintaining the kernel or any of the userland software unless it was internally developed such as a custom installer or various glue code, maintenance scripts, etc. They do not own the libc, the kernel, the shell, any drivers, responsibility for writing security patches, or bug fixes for any code they did not originally write, etc. The distro volunteers or employees of the company in charge of producing the distro may be involved in kernel or other open source softeare development, but it is not required. This may be an unpopular statement, but a Linux distro is not an OS. It is a collection of open source software that tries to be compatible with all of its components. Subject matter experts of all components are usually not involved in its creation. Instead they exist spread out across the entire Linux distro ecosystem. Does Arch Linux have an expert in the virtual memory subsystem of the kernels they ship? Does Gentoo have an expert in the kernel random code? Does Debian have an expert in the glibc codebase? Does Ubuntu have an expert in the bootloader? Does Mint Linux have an expert in the BASH code they ship? I can say with confidence that Suse and Redhat employ experts of many areas of the kernel, glibc, systemd, filesystems, and other components, but not everything. Does FreeBSD/Dragonfly/OpenBSD have an expert or designated owner of the filesystems they ship? Bootloaders? Libc? Kernel timekeeping code? Random? Crypto? VFS? Network stack? NIC drivers? CPU schedulers? Shells and userland utilities? Yes they do. They're OSes, entirely maintained in-project. Just like Windows, OSX, Solaris, etc. OpenBSD is most aggressive here, but unmaintained code usually means nobody is using it and it will be removed. Everything has an owner and is constantly being looked after. In the BSD world it would not be common for a major component to exist long term without an SME joining the project and maintaining it or replacing it. BSDs are OSes, and are mostly independent. You cannot easily port kernel code between them because they have diverged significantly.
    - elros 10y ago
      > An OS is a kernel and userland developed together in its entirety. [citation needed]? How is a Linux distro not an OS? Isn't it the Operating System on whatever machine it's running? If I run Ubuntu or Arch, what OS am I using?
ksec 10y ago
That was against HAMMER 1, which is completely different to HAMMER 2.

jemfinch 10y ago

Reading the diff, I'm neither surprised that this bug existed nor will I be surprised when similar bugs arise. There must be a more readable to write even low-level code like this.

koverstreet 10y ago
Yes, there is. That code needs iterators.
- yoklov 10y ago
  but most of that code isn't iterating. the only parts in that function i see that are iterating ([0] and the similar loop below it) seems straightforward enough to me. i don't see how they would help here unless i don't know what you mean by iterators (assuming c++-style iterators or similar). [0]: http://gitweb.dragonflybsd.org/dragonfly.git/blob/cf297f2cccd7fd102041ebf174af66a31a5ef5ce:/sys/kern/vfs_cluster.c#l1294 http://gitweb.dragonflybsd.org/dragonfly.git/blob/cf297f2ccc...
yoklov 10y ago
honestly, i think it's hard to say this generally without more context into the code. imo nothing there looks too egregious (or at least not abnormally so) for very low level code.

remy_luisant 10y ago

Couldn't they dump out the list of all individual write commands sent to the disk and have seen that the writes are in a suboptimal pattern? This would have been one of the first things I would have done when testing a file system of any kind: Make sure the thing writes what I want to be written and in the way I want it to be written.

forgottenacc57 10y ago
Many problems have obvious solutions in hindsight.
josh64 10y ago
Isn't NCQ meant to do this? I mean reorder the write commands into an optimal order.
koverstreet 10y ago
You don't even need to do anything that hard. All you need to is run basic benchmarks and compare the results to what other filesystems can do, and when yours is about half as fast that should make you go "huh"...
- rurban 10y ago
  Hammer is twice as fast, not half. So huh
  - sleepychu 10y ago
    So it'll now be 4x?
    - rurban 10y ago
      We need benchmarks, and this is the old version only.
cat199 10y ago
People write bugs occasionally. You're talking about the person who spent months tracking down what everyone else thought was a code or compiler bug but actually proved was a subtle CPU bug requiring vendor errata releases, and further, who wrote this log-structured, snapshottable, syncable low-memory using, real-world filesystem from scratch for the highly parallel operating system he has been rearchitecting for over 10 years now. There are consistent status update posts outlining the on disk filesystem structure, as well as its relation to the virtual memory subsystem and the in-kernel parallelism feeding IO writes, as well as constant code commits implementing these things, so I'd reserve the need to back-seat drive here unless I could back it up with a comparable body of work. http://www.theregister.co.uk/2012/03/07/amd_opteron_bug_dragonfly/ http://www.theregister.co.uk/2012/03/07/amd_opteron_bug_drag...

josteink 10y ago

So if I'm reading this patch correctly it's now writing things in blocks instead of as single bytes? Is that it? And, well, yes. Ofcourse that does wonder's for throughput. And I would certainly hope that someone who writes a file-system knows that. Edit: Re-reading the patch it seems like what's being done here is taking a (failed) at attempt at writing in blocks and actually making it write in proper block-sizes. Yay C, I guess.

TheDong 10y ago
Wow, somehow you managed to read the patch without reading the commit message that explains what actually changed. No, you didn't read it correctly.
- josteink 10y ago
  Well yes actually. The fault is completely on me. But in my defence, the code and diff is all colourful and highlighted... While the patch description is "hiding" very subtly in plain sight at the top. When someone is new to any kind of system, their eyes will follow what attracts their attention. I didn't even notice there was a commit message there until you told me. Some minor UI tweaks could probably improve that page greatly :)
  - pmontra 10y ago
    Yes, they should increase the font size of the log section. It's as simple as .log { font-size: large; } using their CSS class and their conventions for font sizes.
  - kzrdude 10y ago
    It's amazing how good we are at filtering information at all levels. I agree with you that the design of the page plays a large part. GitHub probably had more time & reason to optimize this.

HugoDaniel 10y ago

How often does a sequential write happen in an SSD ?

pmontra 10y ago
As often as it happens with HDD, I think. Anyway, with my SSD: I unzipped a 300 MB Raspbian lite zip into a 1.3 GB image yesterday and extracted parts from a 8 GB video with mmpeg last weekend. I expect all of them to be sequential given enough free space on the SDD (same for HDDs.) I also work with docker and vagrant and building those images at half speed can't be good.
digikata 10y ago
Almost always if one wants to optimize...

Upvoter33 10y ago

wow, this is an embarrassing bug. To say it doubles bandwidth makes it sound like an optimization, when in fact it is just (finally) doing what you think it should be doing. Yikes- how long was this doing this and no one noticed?

kzrdude 10y ago
Data loss and corruption is always a lot more embarrassing. Did they have tests that ensure correctness (in data) of the slow version? Then they were already delivering on quality of the file system.