[GH-ISSUE #407] sort_by_inode violates Ord and does not guarantee a total ordering leading to panic #177

New Issue

Closed

opened 2026-06-08 11:26:00 +03:00 by zhus · 8 comments

zhus commented 2026-06-08 11:26:00 +03:00

Owner

Copy Link

Copy Source

Originally created by @d0nutptr on GitHub (Jun 27, 2024).
Original GitHub issue: https://github.com/bootandy/dust/issues/407

Hello!

I happened to run into an interesting edge-case while cleaning up a few projects. While running dust in a folder containing both files and symlinks I encountered this odd panic.

thread 'main' panicked at library/core/src/slice/sort/shared/smallsort.rs:848:5:
Ord violation
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

I debugged the issue and discovered the issue is caused by sort_by_inode in dir_walker.rs. The problem is that the implementation provided does not guarantee a total ordering if both files and symlinks are present. For example:

Assume the folder contains the following nodes with names and inode_devices:

/a - Some(1)
/b - None
/c - Some(0)

There does not exist a total order as there exists no way to order these three files in a way where the following comparisons are satisfied:

* a < b
    * based on name as `b` has no inode device
* a > c
    * based on inode device
* b < c
    * based on name as `b` has no inode device 

I tried to make as small of a testcase as possible, but it was actually really hard to trigger the behavior. This is the smallest test I could create that exhibited the crash:

    #[test]
    fn test_total_ordering_of_sort_by_inode() {
        let mut children = Vec::new();

        children.push(Node {
            name: PathBuf::from_str("a").unwrap(),
            size: 0,
            children: vec![],
            inode_device: Some((19050027, 66310)),
            depth: 0,
        });

        children.push(Node {
            name: PathBuf::from_str("b").unwrap(),
            size: 0,
            children: vec![],
            inode_device: Some((19050112, 66310)),
            depth: 0,
        });

        children.push(Node {
            name: PathBuf::from_str("c").unwrap(),
            size: 0,
            children: vec![],
            inode_device: Some((19050113, 66310)),
            depth: 0,
        });

        children.push(Node {
            name: PathBuf::from_str("d").unwrap(),
            size: 0,
            children: vec![],
            inode_device: Some((19047065, 66310)),
            depth: 0,
        });

        children.push(Node {
            name: PathBuf::from_str("e").unwrap(),
            size: 0,
            children: vec![],
            inode_device: Some((19047066, 66310)),
            depth: 0,
        });

        children.push(Node {
            name: PathBuf::from_str("f").unwrap(),
            size: 0,
            children: vec![],
            inode_device: Some((19048323, 66310)),
            depth: 0,
        });

        children.push(Node {
            name: PathBuf::from_str("g").unwrap(),
            size: 0,
            children: vec![],
            inode_device: None,
            depth: 0,
        });

        children.push(Node {
            name: PathBuf::from_str("h").unwrap(),
            size: 0,
            children: vec![],
            inode_device: Some((19048308, 66310)),
            depth: 0,
        });

        children.push(Node {
            name: PathBuf::from_str("i").unwrap(),
            size: 0,
            children: vec![],
            inode_device: Some((19048309, 66310)),
            depth: 0,
        });

        children.push(Node {
            name: PathBuf::from_str("j").unwrap(),
            size: 0,
            children: vec![],
            inode_device: Some((19048302, 66310)),
            depth: 0,
        });

        children.push(Node {
            name: PathBuf::from_str("k").unwrap(),
            size: 0,
            children: vec![],
            inode_device: Some((19048303, 66310)),
            depth: 0,
        });

        children.push(Node {
            name: PathBuf::from_str("l").unwrap(),
            size: 0,
            children: vec![],
            inode_device: Some((19049996, 66310)),
            depth: 0,
        });

        children.push(Node {
            name: PathBuf::from_str("m").unwrap(),
            size: 0,
            children: vec![],
            inode_device: Some((19048314, 66310)),
            depth: 0,
        });

        children.push(Node {
            name: PathBuf::from_str("n").unwrap(),
            size: 0,
            children: vec![],
            inode_device: Some((19048315, 66310)),
            depth: 0,
        });

        children.push(Node {
            name: PathBuf::from_str("o").unwrap(),
            size: 0,
            children: vec![],
            inode_device: Some((19048318, 66310)),
            depth: 0,
        });

        children.push(Node {
            name: PathBuf::from_str("p").unwrap(),
            size: 0,
            children: vec![],
            inode_device: None,
            depth: 0,
        });

        children.push(Node {
            name: PathBuf::from_str("q").unwrap(),
            size: 0,
            children: vec![],
            inode_device: Some((19049674, 66310)),
            depth: 0,
        });

        children.push(Node {
            name: PathBuf::from_str("r").unwrap(),
            size: 0,
            children: vec![],
            inode_device: Some((19046994, 66310)),
            depth: 0,
        });

        children.push(Node {
            name: PathBuf::from_str("s").unwrap(),
            size: 0,
            children: vec![],
            inode_device: Some((19046995, 66310)),
            depth: 0,
        });

        children.push(Node {
            name: PathBuf::from_str("t").unwrap(),
            size: 0,
            children: vec![],
            inode_device: Some((19047666, 66310)),
            depth: 0,
        });

        children.push(Node {
            name: PathBuf::from_str("u").unwrap(),
            size: 0,
            children: vec![],
            inode_device: Some((19050145, 66310)),
            depth: 0,
        });

        children.sort_by(sort_by_inode);
    }

Originally created by @d0nutptr on GitHub (Jun 27, 2024). Original GitHub issue: https://github.com/bootandy/dust/issues/407 Hello! I happened to run into an interesting edge-case while cleaning up a few projects. While running `dust` in a folder containing both files and symlinks I encountered this odd panic.  ``` thread 'main' panicked at library/core/src/slice/sort/shared/smallsort.rs:848:5: Ord violation note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace ``` I debugged the issue and discovered the issue is caused by `sort_by_inode` in `dir_walker.rs`. The problem is that the implementation provided does not guarantee a total ordering if both files and symlinks are present. For example: Assume the folder contains the following nodes with names and `inode_device`s: ``` /a - Some(1) /b - None /c - Some(0) ``` There does not exist a total order as there exists no way to order these three files in a way where the following comparisons are satisfied: ``` * a < b * based on name as `b` has no inode device * a > c * based on inode device * b < c * based on name as `b` has no inode device ``` I tried to make as small of a testcase as possible, but it was actually really hard to trigger the behavior. This is the smallest test I could create that exhibited the crash: ```rust #[test] fn test_total_ordering_of_sort_by_inode() { let mut children = Vec::new(); children.push(Node { name: PathBuf::from_str("a").unwrap(), size: 0, children: vec![], inode_device: Some((19050027, 66310)), depth: 0, }); children.push(Node { name: PathBuf::from_str("b").unwrap(), size: 0, children: vec![], inode_device: Some((19050112, 66310)), depth: 0, }); children.push(Node { name: PathBuf::from_str("c").unwrap(), size: 0, children: vec![], inode_device: Some((19050113, 66310)), depth: 0, }); children.push(Node { name: PathBuf::from_str("d").unwrap(), size: 0, children: vec![], inode_device: Some((19047065, 66310)), depth: 0, }); children.push(Node { name: PathBuf::from_str("e").unwrap(), size: 0, children: vec![], inode_device: Some((19047066, 66310)), depth: 0, }); children.push(Node { name: PathBuf::from_str("f").unwrap(), size: 0, children: vec![], inode_device: Some((19048323, 66310)), depth: 0, }); children.push(Node { name: PathBuf::from_str("g").unwrap(), size: 0, children: vec![], inode_device: None, depth: 0, }); children.push(Node { name: PathBuf::from_str("h").unwrap(), size: 0, children: vec![], inode_device: Some((19048308, 66310)), depth: 0, }); children.push(Node { name: PathBuf::from_str("i").unwrap(), size: 0, children: vec![], inode_device: Some((19048309, 66310)), depth: 0, }); children.push(Node { name: PathBuf::from_str("j").unwrap(), size: 0, children: vec![], inode_device: Some((19048302, 66310)), depth: 0, }); children.push(Node { name: PathBuf::from_str("k").unwrap(), size: 0, children: vec![], inode_device: Some((19048303, 66310)), depth: 0, }); children.push(Node { name: PathBuf::from_str("l").unwrap(), size: 0, children: vec![], inode_device: Some((19049996, 66310)), depth: 0, }); children.push(Node { name: PathBuf::from_str("m").unwrap(), size: 0, children: vec![], inode_device: Some((19048314, 66310)), depth: 0, }); children.push(Node { name: PathBuf::from_str("n").unwrap(), size: 0, children: vec![], inode_device: Some((19048315, 66310)), depth: 0, }); children.push(Node { name: PathBuf::from_str("o").unwrap(), size: 0, children: vec![], inode_device: Some((19048318, 66310)), depth: 0, }); children.push(Node { name: PathBuf::from_str("p").unwrap(), size: 0, children: vec![], inode_device: None, depth: 0, }); children.push(Node { name: PathBuf::from_str("q").unwrap(), size: 0, children: vec![], inode_device: Some((19049674, 66310)), depth: 0, }); children.push(Node { name: PathBuf::from_str("r").unwrap(), size: 0, children: vec![], inode_device: Some((19046994, 66310)), depth: 0, }); children.push(Node { name: PathBuf::from_str("s").unwrap(), size: 0, children: vec![], inode_device: Some((19046995, 66310)), depth: 0, }); children.push(Node { name: PathBuf::from_str("t").unwrap(), size: 0, children: vec![], inode_device: Some((19047666, 66310)), depth: 0, }); children.push(Node { name: PathBuf::from_str("u").unwrap(), size: 0, children: vec![], inode_device: Some((19050145, 66310)), depth: 0, }); children.sort_by(sort_by_inode); } ```

zhus closed this issue 2026-06-08 11:26:00 +03:00

zhus commented 2026-06-08 11:26:00 +03:00

Author

Owner

Copy Link

Copy Source

@bootandy commented on GitHub (Jun 28, 2024):

That's interesting. I'll look into this.

Just trying that test and set it to run in a loop, I haven't seen it fail yet. I'm using ubuntu, which OS did you use ? & Does it take several runs to fail ?

<!-- gh-comment-id:2195750384 --> @bootandy commented on GitHub (Jun 28, 2024): That's interesting. I'll look into this. Just trying that test and set it to run in a loop, I haven't seen it fail yet. I'm using ubuntu, which OS did you use ? & Does it take several runs to fail ?

zhus commented 2026-06-08 11:26:00 +03:00

Author

Owner

Copy Link

Copy Source

@d0nutptr commented on GitHub (Jun 28, 2024):

Hey! Yea it can take a few goes in practice to crash.

It is exceedingly rare to find a situation where this happens in practice.

I fuzzed millions of configurations of files to see if i could make a smaller poc to send and came up with nothing.

If you run the above provided test case, though, it should be 100% reproducible.

<!-- gh-comment-id:2195752895 --> @d0nutptr commented on GitHub (Jun 28, 2024): Hey! Yea it can take a few goes in practice to crash. It is **exceedingly rare** to find a situation where this happens in practice. I fuzzed millions of configurations of files to see if i could make a smaller poc to send and came up with nothing. If you run the above provided test case, though, it should be 100% reproducible.

zhus commented 2026-06-08 11:26:00 +03:00

Author

Owner

Copy Link

Copy Source

@d0nutptr commented on GitHub (Jun 28, 2024):

Oh, and yes I use ubuntu :)

<!-- gh-comment-id:2195753491 --> @d0nutptr commented on GitHub (Jun 28, 2024): Oh, and yes I use ubuntu :)

zhus commented 2026-06-08 11:26:00 +03:00

Author

Owner

Copy Link

Copy Source

@bootandy commented on GitHub (Jun 28, 2024):

I see how this could happen. So this is genuine. (I just can't yet reproduce it). Going to have to think about this.

We could catch the panic and sort by name if that happens.

<!-- gh-comment-id:2195757657 --> @bootandy commented on GitHub (Jun 28, 2024): I see how this could happen. So this is genuine. (I just can't yet reproduce it). Going to have to think about this. We could catch the panic and sort by name if that happens.

zhus commented 2026-06-08 11:26:00 +03:00

Author

Owner

Copy Link

Copy Source

@bootandy commented on GitHub (Jun 28, 2024):

This is helping me think about it: I codifed your description in the issue:

    #[test]
    fn test_total_ordering_of_sort_by_inode() {
        let a = Node {
            name: PathBuf::from_str("a").unwrap(),
            size: 0,
            children: vec![],
            inode_device: Some((3, 66310)),
            depth: 0,
        };

        let b = Node {
            name: PathBuf::from_str("b").unwrap(),
            size: 0,
            children: vec![],
            inode_device: None,
            depth: 0,
        };

        let c = Node {
            name: PathBuf::from_str("c").unwrap(),
            size: 0,
            children: vec![],
            inode_device: Some((1, 66310)),
            depth: 0,
        };

        assert_eq!(sort_by_inode(&a, &b), Ordering::Less); //a < b
        assert_eq!(sort_by_inode(&a, &c), Ordering::Greater); // a > c
        assert_eq!(sort_by_inode(&c, &b), Ordering::Greater); // c > b
        // Transitivity fail

        assert_eq!(sort_by_inode(&c, &a), Ordering::Less);
        assert_eq!(sort_by_inode(&a, &c), Ordering::Greater);
        assert_eq!(sort_by_inode(&c, &a), Ordering::Less);
    }

<!-- gh-comment-id:2195775891 --> @bootandy commented on GitHub (Jun 28, 2024): This is helping me think about it: I codifed your description in the issue: ``` #[test] fn test_total_ordering_of_sort_by_inode() { let a = Node { name: PathBuf::from_str("a").unwrap(), size: 0, children: vec![], inode_device: Some((3, 66310)), depth: 0, }; let b = Node { name: PathBuf::from_str("b").unwrap(), size: 0, children: vec![], inode_device: None, depth: 0, }; let c = Node { name: PathBuf::from_str("c").unwrap(), size: 0, children: vec![], inode_device: Some((1, 66310)), depth: 0, }; assert_eq!(sort_by_inode(&a, &b), Ordering::Less); //a < b assert_eq!(sort_by_inode(&a, &c), Ordering::Greater); // a > c assert_eq!(sort_by_inode(&c, &b), Ordering::Greater); // c > b // Transitivity fail assert_eq!(sort_by_inode(&c, &a), Ordering::Less); assert_eq!(sort_by_inode(&a, &c), Ordering::Greater); assert_eq!(sort_by_inode(&c, &a), Ordering::Less); } ```

zhus commented 2026-06-08 11:26:00 +03:00

Author

Owner

Copy Link

Copy Source

@bootandy commented on GitHub (Jun 28, 2024):

https://github.com/bootandy/dust/pull/408

does this look like it would fix it ?

<!-- gh-comment-id:2195790131 --> @bootandy commented on GitHub (Jun 28, 2024): https://github.com/bootandy/dust/pull/408 does this look like it would fix it ?

zhus commented 2026-06-08 11:26:00 +03:00

Author

Owner

Copy Link

Copy Source

@d0nutptr commented on GitHub (Jun 28, 2024):

I think it would!

I wrote a simple hardness to formally verify the Ord property so let me try this new implementation to see if it can find a violation.

<!-- gh-comment-id:2195833449 --> @d0nutptr commented on GitHub (Jun 28, 2024): I think it would! I wrote a simple hardness to formally verify the Ord property so let me try this new implementation to see if it can find a violation.

zhus commented 2026-06-08 11:26:00 +03:00

Author

Owner

Copy Link

Copy Source

@d0nutptr commented on GitHub (Jun 28, 2024):

I assume I wrote a relatively reasonable definition to check total order here, but it looks like it verified! 🚢 it

<!-- gh-comment-id:2195899005 --> @d0nutptr commented on GitHub (Jun 28, 2024): I assume I wrote a relatively reasonable definition to check total order here, but it looks like it verified! :ship: it 

zhus referenced this issue 2026-06-08 11:27:22 +03:00

[PR #177] [MERGED] Minor & increment version #345

Sign in to join this conversation.

No Branch/Tag Specified

Branches Tags

master

release

rmbuild

build2

build

config_collapse

maybe_build

up

tweak

bye_bye_directories

deps

return_1

fix_depth_test

stay

style

clean2

upgrade_lib

use_stderr_for_logs

other2

same_dir_names2

same_dir_names

skip_total_bars

i_wanna_go_fast

test

clean_tests

clean_json

aarch_build

kilos2_refactor

kilos2

cargo_update2

aarch_build2

fix2

links

fix_error_on_thread_creation5

fix_error_on_thread_creation4

fix_error_on_thread_creation3

fix_error_on_thread_creation2

fix_error_on_thread_creation

depth_refactor2

v1.2.4

v1.2.3

v1.2.2

v1.2.1

v1.2.0

v1.1.2

v1.1.1

v1.1.0

v1.0.0

v0.9.0

v0.8.6

v0.8.5

v0.8.4

v0.8.3

v0.8.2

v0.8.1

v0.8.1-alpha.2

v0.8.1-alpha.1

v0.8.0

v0.7.1.alpha4

v0.7.1.alpha3

v0.7.1.alpha

v0.7.5

v0.7.0

v0.6.2

v0.6.1

v0.6.0

v0.5.4

v0.5.3

v0.5.2

v0.5.1

v0.5.0

v0.4.5.0

v0.4.41

v0.4.4

v0.4.3

v0.4.2

v0.4.1.2

v0.4.1.1

v0.4.0.1

v0.4.0

v0.4.1

v0.3.1

v0.3.0

v0.2.3

v0.2.2

v0.2.1

v0.2.0

v0.1.2

untagged-1499119fdec1dec70238

v0.1.1

0.1.0

Labels

Clear labels

good first issue

help wanted

pull-request

Mirrored from GitHub Pull Request

windows help wanted

No Label

Milestone

No items

No Milestone

Projects

Clear projects

No project

Assignees

Clear assignees

zhus (Sergey Zhukov)

No Assignees

1 Participants

Notifications

Subscribe

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: bootandy/archived-dust#177