Path: ...!Xl.tags.giganews.com!local-1.nntp.ord.giganews.com!nntp.brightview.co.uk!news.brightview.co.uk.POSTED!not-for-mail
NNTP-Posting-Date: Thu, 15 Aug 2024 05:56:45 +0000
From: Mark Summerfield <mark@qtrac.eu>
Subject: why does bsearch segfault on custom strcmp when qsort works fine?
Newsgroups: comp.lang.c
MIME-Version: 1.0
User-Agent: Pan/0.154 (Izium; 517acf4)
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Message-ID: <UQWdnfwQxtYABSD7nZ2dnZfqnPadnZ2d@brightview.co.uk>
Date: Thu, 15 Aug 2024 05:56:45 +0000
Lines: 138
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-OCMzTm6lqKiPRgRH8SmwANSzct+Kf8gzd/KAcYxCmBsz0rKLLOhwBlC1FgjPqX4ZvIfc/E9x5/3hNBg!GnvGZFRNCIsxzMjmV3+sve3IZLKooDt7PXsTXnu515hWcPzK/cDuSkzMTPEeU+Hkq0uHiYamE0Ag!f99QWmlBAM1Zm3A6b8kDPDVFHA==
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
Bytes: 5534

I have a program (complete source at the end) which correctly outputs this:

["charlie" "foxtrot" "oscar" "echo" "alpha" "golf" "tango" "delta" "bravo"]
["alpha" "bravo" "charlie" "delta" "echo" "foxtrot" "golf" "oscar" "tango"]
check_array OK
check_index_found true OK
check_index_found false OK

However, if you uncomment the "//#define BUG" line, the output (in gdb) is this:

(gdb) run
Starting program: /home/mark/tmp/mycmpstr/mycmpstr 
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
["charlie" "foxtrot" "oscar" "echo" "alpha" "golf" "tango" "delta" "bravo"]
["alpha" "bravo" "charlie" "delta" "echo" "foxtrot" "golf" "oscar" "tango"]
check_array OK

Program received signal SIGSEGV, Segmentation fault.
__strcmp_avx2 () at ../sysdeps/x86_64/multiarch/strcmp-avx2.S:283
283	../sysdeps/x86_64/multiarch/strcmp-avx2.S: No such file or directory.
(gdb) bt
#0  __strcmp_avx2 () at ../sysdeps/x86_64/multiarch/strcmp-avx2.S:283
#1  0x00005555555553e0 in mystrcmp (s=0x555555556030, t=0x7fffffffde10) at mycmpstr.c:50
#2  0x00007ffff7e0a53c in __GI_bsearch (__key=0x555555556030, __base=0x7fffffffddf0, 
    __nmemb=<optimized out>, __size=8, __compar=0x5555555553b7 <mystrcmp>)
    at ../bits/stdlib-bsearch.h:33
#3  0x0000555555555317 in main () at mycmpstr.c:30

The difference is that without BUG defined I use my own binary search,
but with BUG defined I use bsearch.

Here's the complete source ~100 LOC:

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//#define BUG

int mystrcmp(const void* s, const void* t);
size_t search(const char* s, char** array, size_t size, bool* found);
void dump(char** array, size_t size);
void check_array(char** actual, char** expected, size_t size);
void check_index_found(size_t a, size_t e, bool afound, bool efound);

int main() {
    char* expected[] = {"alpha",   "bravo", "charlie", "delta", "echo",
                        "foxtrot", "golf",  "oscar",   "tango"};
    char* words[] = {"charlie", "foxtrot", "oscar", "echo", "alpha",
                     "golf",    "tango",   "delta", "bravo"};
    const size_t size = sizeof(words) / sizeof(char*);
    dump(words, size);
    // mystrcmp works fine:
    qsort(words, size, sizeof(char*), mystrcmp);
    dump(words, size);
    check_array(words, expected, size);

    size_t index = 0;
    bool found = false;
#ifdef BUG
    // mystrcmp segfaults:
    char* p = bsearch("oscar", words, size, sizeof(char*), mystrcmp);
    index = p - words[0];
    found = p != NULL;
#else
    index = search("oscar", words, size, &found);
#endif
    check_index_found(index, 7, found, true);

    index = 0;
    found = false;
#ifdef BUG
    p = bsearch("X!@", words, size, sizeof(char*), mystrcmp);
    found = p != NULL;
#else
    index = search("X!@", words, size, &found);
#endif
    check_index_found(index, 0, found, false);
}

int mystrcmp(const void* s, const void* t) {
    return strcmp(*(const char**)s, *(const char**)t);
}

size_t search(const char* s, char** array, size_t size, bool* found) {
    *found = false;
    size_t index = 0;
    size_t low = 0;
    size_t high = size - 1;
    while (high && low <= high) {
        size_t mid = low + ((high - low) / 2);
        const char* value = array[mid];
        int cmp = strcmp(value, s);
        if (cmp == 0) {
            index = mid;
            *found = true;
            break;
        }
        if (cmp < 0)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return index;
}

void dump(char** array, size_t size) {
    printf("[");
    for (size_t i = 0; i < size; ++i) {
        printf("\"%s\"", array[i]);
        if (i + 1 < size)
            printf(" ");
    }
    printf("]\n");
}

void check_array(char** actual, char** expected, size_t size) {
    bool ok = true;
    for (size_t i = 0; i < size; ++i) {
        if (strcmp(actual[i], expected[i])) {
            printf("ERROR: \"%s\" != \"%s\"\n", actual[i], expected[i]);
            ok = false;
        }
    }
    if (ok)
        printf("check_array OK\n");
}

void check_index_found(size_t a, size_t e, bool afound, bool efound) {
    if (afound && efound && a != e)
        printf("ERROR: %zu != %zu\n", a, e);
    else if (afound != efound)
        printf("ERROR: %d != %d\n", afound, efound);
    else
        printf("check_index_found %s OK\n", afound ? "true" : "false");
}