rust code (with no unsafe) keeps segfaulting (musl)

related code main.rs

fn main() {
    println!("{:?}",mimey::binary_search("zsh"));
}

lib.rs

// MIME is a [(&str, &str); 670]
fn strcmp(x: &[u8], z: &[u8]) -> isize {
    if x.is_empty() || z.is_empty() {
        return 0;
    }
    if x[0] != z[0] {
        // clamp (dont want to skip an index now do i)
        return ((x[0] as isize) - z[0] as isize).clamp(-1, 1);
    }
    strcmp(&x[1..], &z[1..])
}

// it segfaults. somehow
fn bins(k: &[u8], ci: usize) -> Option<&str> {
    let sp = strcmp(k, MIME[ci].0.as_bytes());
    if sp == 0 {
        return Some(MIME[ci].1);
    }
    if ci == 0 || ci == MIME.len() - 1 {
        return None;
    }
    bins(k, ci.checked_add_signed(sp)?)
}

pub fn binary_search(k: &str) -> Option<&str> {
    bins(k.as_bytes(), MIME.len() / 2)
}

uname:

Linux r0 6.9.1-0-edge #1-Alpine SMP PREEMPT_DYNAMIC

rustc -vV:

rustc 1.78.0 (9b00956e5 2024-04-29) (Alpine Linux 1.78.0-r0)
binary: rustc
commit-hash: 9b00956e56009bab2aa15d7bff10916599e3d6d6
commit-date: 2024-04-29
host: x86_64-alpine-linux-musl
release: 1.78.0
LLVM version: 17.0.6

lldb:

* thread #1, name = 'mimey', stop reason = signal SIGSEGV: address not mapped to object (fault address: 0x7fffff7fe9a8)
    frame #0: 0x0000555555563d01 mimey`mimey::bins::hee7c9bb096833bc5(k=(data_ptr = "", length = 1), ci=1) at lib.rs:706
   703  }
   704  
   705  // it segfaults. somehow
-> 706  fn bins(k: &[u8], ci: usize) -> Option<&str> {
   707      let sp = strcmp(k, MIME[ci].0.as_bytes());
   708      if sp == 0 {
   709          return Some(MIME[ci].1);

MIME is defined in lib.rs. I don't have any idea why k seems to be empty. This is part of a mime-guessing library I've been writing for fun..

Solution

Not enough information to be 100%, but there appears to be a logical error in your code that can result in an infinite loop, which would overflow the stack and then SIGSEGV.

Imagine Mime is defined as so:

const MIME: [(&'static str, &'static str); 4] =
    [("000", "?"), ("002", "?"), ("006", "?"), ("007", "?")];

then, binary_search("005") will never exit, overflow the stack, and throw SIGSEGV. Specifically, you enter a state where bins(k, 2) calls bins(k, 3), which calls bins(k, 2).

Without knowing the exact values of MIME it's impossible to be sure, but I suspect this is what is happening. Add a line printing sp before your sp == 0 check, and you should see alternating 1, and -1 values.