hexdump(1): Speed up -s flag on devices

[kevans]

Summary

Using the -s flag on devices is extraordinarily slow due to using
fseek(3) a little too conservatively. Address this by using fseek on character/block
devices as well, falling back to getchar(3) only if we fail to seek or we're operating
on tape drives, where fseek may succeed while not actually supported.

This is dependent upon D10893 and D10937.

PR: 86485
Submitted by: arundel@, then massaged a little bit

Test Plan

Run test cases in PR 86485, observe dramatic improvements in speed from
many seconds down to practically nothing.

[cem]

I think we should just fix the tape devices that don't support seeking to return an error for fseek() instead.

[kevans]

Is that actually feasible, though? From what I can tell/know (admittedly little), there's just a handful of drivers supporting heaps of tape devices, and we'd have to accumulate a whitelist of those tape devices that *do* properly support seeking, which will then break for devices that we don't know about that do support seeking when one actually tries to fseek on it -- if it's even that black and white of an issue. =(

[cem]

In D10939#226532, @kevans91_ksu.edu wrote:

Is that actually feasible, though? From what I can tell/know (admittedly little), there's just a handful of drivers supporting heaps of tape devices, and we'd have to accumulate a whitelist of those tape devices that *do* properly support seeking, which will then break for devices that we don't know about that do support seeking when one actually tries to fseek on it -- if it's even that black and white of an issue. =(

Seems more feasible than changing every program that performs a seek to check for tape devices and try and work around it somehow. We don't even need the whitelist, necessarily — every program that wants to correctly interact with tapes today must pretend fseek is broken and seek manually with reads. We could have fseek() error for all tape devices without breaking programs that handle tape devices in this way. The whitelist is probably preferable, and there would need to be some mechanism to workaround the list (ioctl or sysctl).

fseek() not working but returning success is a broken abstraction. That's the right place to fix it, IMO.

[kevans]

In D10939#226553, @cem wrote:

Seems more feasible than changing every program that performs a seek to check for tape devices and try and work around it somehow. We don't even need the whitelist, necessarily — every program that wants to correctly interact with tapes today must pretend fseek is broken and seek manually with reads. We could have fseek() error for all tape devices without breaking programs that handle tape devices in this way. The whitelist is probably preferable, and there would need to be some mechanism to workaround the list (ioctl or sysctl).

Indeed it does seem more feasible, but then again- how common of a problem is it? Most other applications I've looked at have an opt-in for fseek, but their performance is nowhere near as terrible as it is here with the getchar alternative.

fseek() not working but returning success is a broken abstraction. That's the right place to fix it, IMO.

I'm also inclined to agree, but something else: can we really rely on it doing the right thing? We can fix it here in FreeBSD, but relying on that (undefined behavior, according to POSIX) puts a damper on portability and ability to cherry-pick this improvement on other platforms.

That same argument could eliminate the ability to do this optimization at all, since mailing list entries I've stumbled upon seem to suggest that it's a potential problem with other media types as well. This is also noted in the original PR ("... hexdump will not fail in case it
is being run against a device without a medium (DVD or Blue-ray) inserted."), but I'm not sure if *that* case is necessarily worth worrying about since hexdump will not provide anything worthwhile to begin with if no medium is present.

I *do* think that these improvements to fseek should be made (independently), but I'm afraid that's not the end of the problems down this road until everyone (within and outside of FreeBSD) makes the effort to take on the same interpretation of the undefined behavior.

[cem]

In D10939#226568, @kevans91_ksu.edu wrote:

Indeed it does seem more feasible, but then again- how common of a problem is it? Most other applications I've looked at have an opt-in for fseek, but their performance is nowhere near as terrible as it is here with the getchar alternative.

I guess we could improve the fallback in hexdump. I'm not really familiar with the code base. :-)

fseek() not working but returning success is a broken abstraction. That's the right place to fix it, IMO.

I'm also inclined to agree, but something else: can we really rely on it doing the right thing? We can fix it here in FreeBSD, but relying on that (undefined behavior, according to POSIX) puts a damper on portability and ability to cherry-pick this improvement on other platforms.

Does POSIX really say fseek() can silently fail (returning success)? None of the manual pages (Linux, FreeBSD) seem to mention that. Given that, I'd be *shocked* if programmers are aware of it. (I wasn't :-).)

That same argument could eliminate the ability to do this optimization at all, since mailing list entries I've stumbled upon seem to suggest that it's a potential problem with other media types as well. This is also noted in the original PR ("... hexdump will not fail in case it
is being run against a device without a medium (DVD or Blue-ray) inserted."), but I'm not sure if *that* case is necessarily worth worrying about since hexdump will not provide anything worthwhile to begin with if no medium is present.

Right. We could improve the fallback case in hexdump instead, I guess?

I *do* think that these improvements to fseek should be made (independently), but I'm afraid that's not the end of the problems down this road until everyone (within and outside of FreeBSD) makes the effort to take on the same interpretation of the undefined behavior.

Sure. My read is that the only sane way to handle that is with an EOPNOTSUPP or similar. I'd suggest investigating what we do, what Linux does, try and reconcile them, and then submit a ticket to the Austin group to define the behavior of fseek on devices that are incapable of seeking (as an error status). POSIX is a living document, to some extent. I think ed@ has some experience with this if you want to ask him about it.

[kevans]

In D10939#226626, @cem wrote:

In D10939#226568, @kevans91_ksu.edu wrote:

Indeed it does seem more feasible, but then again- how common of a problem is it? Most other applications I've looked at have an opt-in for fseek, but their performance is nowhere near as terrible as it is here with the getchar alternative.

I guess we could improve the fallback in hexdump. I'm not really familiar with the code base. :-)

Instead of checking for a tape device, detect the lack of movement via ftell() and fallback to getchar()?

fseek() not working but returning success is a broken abstraction. That's the right place to fix it, IMO.

I'm also inclined to agree, but something else: can we really rely on it doing the right thing? We can fix it here in FreeBSD, but relying on that (undefined behavior, according to POSIX) puts a damper on portability and ability to cherry-pick this improvement on other platforms.

Does POSIX really say fseek() can silently fail (returning success)? None of the manual pages (Linux, FreeBSD) seem to mention that. Given that, I'd be *shocked* if programmers are aware of it. (I wasn't :-).)

In not so many words:

POSIX wrote (http://pubs.opengroup.org/onlinepubs/009696899/functions/fseek.html):

The behavior of fseek() on devices which are incapable of seeking is implementation-defined. The value of the file offset associated with such a device is undefined.

Nowhere else does it actually forbid a call to silently fail, just that it must fail on read/write errors.

I *do* think that these improvements to fseek should be made (independently), but I'm afraid that's not the end of the problems down this road until everyone (within and outside of FreeBSD) makes the effort to take on the same interpretation of the undefined behavior.

Sure. My read is that the only sane way to handle that is with an EOPNOTSUPP or similar. I'd suggest investigating what we do, what Linux does, try and reconcile them, and then submit a ticket to the Austin group to define the behavior of fseek on devices that are incapable of seeking (as an error status). POSIX is a living document, to some extent. I think ed@ has some experience with this if you want to ask him about it.

Reading around on mailing lists seemed to indicate that Linux tends to exhibit the same behavior as we do, but (IIRC) none of that sounded very authoritative. A consistent ENXIO would be nice here, since that's supposed to indicate that the device is nonexistent or the request was outside of the capabilities of the device.

I'm not entirely certain why my above POSIX quote was not rewritten or removed in later revisions. In the revision I linked, ENXIO appears to only be returned in certain conditions. It was later revised to its own failure condition after the other ones. I would link to it here, but the new format uses frames in a painful way that isn't entirely useful. =(

[cem]

In D10939#226634, @kevans91_ksu.edu wrote:

Instead of checking for a tape device, detect the lack of movement via ftell() and fallback to getchar()?

The same POSIX page says that the seek position (result of ftell()) is also equally implementation defined on devices that do not support seeking :-(.

POSIX wrote (http://pubs.opengroup.org/onlinepubs/009696899/functions/fseek.html):

The behavior of fseek() on devices which are incapable of seeking is implementation-defined. The value of the file offset associated with such a device is undefined.

Nowhere else does it actually forbid a call to silently fail, just that it must fail on read/write errors.

Right. But I would still be surprised if this is widely known. :-)

I *do* think that these improvements to fseek should be made (independently), but I'm afraid that's not the end of the problems down this road until everyone (within and outside of FreeBSD) makes the effort to take on the same interpretation of the undefined behavior.

Sure. My read is that the only sane way to handle that is with an EOPNOTSUPP or similar. I'd suggest investigating what we do, what Linux does, try and reconcile them, and then submit a ticket to the Austin group to define the behavior of fseek on devices that are incapable of seeking (as an error status). POSIX is a living document, to some extent. I think ed@ has some experience with this if you want to ask him about it.

Reading around on mailing lists seemed to indicate that Linux tends to exhibit the same behavior as we do, but (IIRC) none of that sounded very authoritative. A consistent ENXIO would be nice here, since that's supposed to indicate that the device is nonexistent or the request was outside of the capabilities of the device.

Yeah, I'd like something like that. Really any error status is probably ok, but it would be convenient for application developers if the open source unixes picked one to agree on.

I'm not entirely certain why my above POSIX quote was not rewritten or removed in later revisions. In the revision I linked, ENXIO appears to only be returned in certain conditions. It was later revised to its own failure condition after the other ones. I would link to it here, but the new format uses frames in a painful way that isn't entirely useful. =(

[kevans]

In D10939#226658, @cem wrote:

In D10939#226634, @kevans91_ksu.edu wrote:

Instead of checking for a tape device, detect the lack of movement via ftell() and fallback to getchar()?

The same POSIX page says that the seek position (result of ftell()) is also equally implementation defined on devices that do not support seeking :-(.

Ugh. =(

[cem]

Ok with this mitigation, but I'd really like to see devices produce a seek error instead.

usr.bin/hexdump/display.c

413 ↗

(On Diff #28868)

style nit: spaces around &

430–431 ↗

(On Diff #28868)

Could this be done in chunks, rather than char at a time?

[kevans]

usr.bin/hexdump/display.c

430–431 ↗

(On Diff #28868)

Sure -- we could throw a stack-allocated buffer for some reasonable chunk size and fread it.

Determining a reasonable chunk size is a little more complicated, though, since this is purely interpretation of the -s flag. I'd be almost inclined to give it a chunk size of, say, 512 bytes and call it good there unless given a compelling argument otherwise.

[kevans]

usr.bin/hexdump/display.c

430–431 ↗

(On Diff #28868)

I implemented it with some chunking and forcing everything through the noseek path, but I'm not finding any kind of performance gains to be had to justify the additional complexity. =(

[kevans]

usr.bin/hexdump/display.c

413 ↗

(On Diff #28868)

Will fix prior to commit