Легкий ахтунг внутрях Linux
Захотелось заглянуть внутрь libc Ubuntu Linux 10.04 на реализацию функции bsearch, а там небольшая проблемка:
void * bsearch (const void *key, const void *base, size_t nmemb, size_t size, int (*compar) (const void *, const void *)) { size_t l, u, idx; const void *p; int comparison; l = 0; u = nmemb; while (l < u) { idx = (l + u) / 2; p = (void *) (((const char *) base) + (idx * size)); comparison = (*compar) (key, p); if (comparison < 0) u = idx; else if (comparison > 0) l = idx + 1; else return (void *) p; } return NULL; }
Проблема в строке
idx = (l + u) / 2;
При достаточно больших значениях nmemb и поиске ключа из “верхнего” раздела массива, здесь может возникнуть переполнение (если компилятор не отслеживает такие ситуации), и соответственно функция будет зацикливаться.
Конечно, это касается действительно огромных массивов, с более чем 231 элементов для 32-битных систем (где размер size_t равен 4 байтам).
Вариант bsearch во FreeBSD 7.1 не имеет этой проблемы:
void * bsearch(key, base0, nmemb, size, compar) const void *key; const void *base0; size_t nmemb; size_t size; int (*compar)(const void *, const void *); { const char *base = base0; size_t lim; int cmp; const void *p; for (lim = nmemb; lim != 0; lim >>= 1) { p = base + (lim >> 1) * size; cmp = (*compar)(key, p); if (cmp == 0) return ((void *)p); if (cmp > 0) { /* key > p: move right */ base = (char *)p + size; lim--; } /* else move left */ } return (NULL); }
Запись опубликована СоНоты.Вы можете оставить комментарии здесь или тут