В проекте, над которым я сейчас работаю (на языке C), мы храним хеш-таблицу некоторых непрозрачных объектов. Мы используем DPDK для ввода-вывода в нашем приложении (версия 16.07.2, к сожалению), и мы используем код rte_hash для хеширования нашего объекта. Проблема в том, что объекты, которые мы хотим хешировать, имеют странные неокругленные размеры, например, 83 (или 18, как в приведенном ниже примере), а средство очистки адресов жалуется на переполнение кучи-буфера (при чтении) — пытаясь прочитать байты после конец области:
==4926==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60300007a9c0 at pc 0x000000451573 bp 0x7fff69175040 sp 0x7fff69175030
READ of size 4 at 0x60300007a9c0 thread T10ESC[1mESC[0m
#0 0x451572 in __rte_jhash_2hashes /path/to/../dpdk/usr/include/dpdk/rte_jhash.h:155
#1 0x452bb6 in rte_jhash_2hashes /path/to/../dpdk/usr/include/dpdk/rte_jhash.h:266
#2 0x452c75 in rte_jhash /path/to/../dpdk/usr/include/dpdk/rte_jhash.h:309
0x60300007a9c2 is located 0 bytes to the right of 18-byte region [0x60300007a9b0,0x603
00007a9c2)
Насколько я могу судить, проблема здесь, в rte_jhash.h (см. здесь код в последнем DPDK, насколько я могу судить, он не изменился: http://dpdk.org/doc/api/rte__jhash_8h_source.html):
case 6:
b += k[1] & LOWER16b_MASK; a += k[0]; break;
Код считывает k[1] как uint32_t, а затем объединяет значение И так, что последние 2 байта отбрасываются. Насколько я могу судить, средство очистки адресов жалуется на чтение uint32_t, когда только первые 2 байта помечены как доступные для чтения. В этом есть смысл, но код rte_hash может похвастаться тем, что может использовать ключи любого размера. Итак, мой вопрос: эта проблема только теоретическая? Или можно было бы вызвать сбой с этим, может быть, с объектом странного размера, который оказался в конце страницы? Мы работаем на x86-64.
Несколько месяцев назад изменение в DPDK добавило кое-что в комментарии по этому поводу (см. noreferrer">http://dpdk.org/browse/dpdk/commit/lib/librte_hash?id=0c57f40e66c8c29c6c92a7b0dec46fcef5584941), но я ожидал, что формулировка будет более жесткой, если возможен сбой.
ОБНОВЛЕНИЕ: пример кода для воспроизведения предупреждения. Скомпилировать с:
gcc -o jhash_malloc -Wall -g -fsanitize=address -I /path/to/dpdk/x86_64-native-linuxapp-gcc/include/ jhash_malloc.c
И код:
#include <stdio.h>
#include <rte_jhash.h>
#include <stdlib.h>
#include <unistd.h>
int main()
{
size_t strSize = 13;
char *str = malloc(strSize);
memset(str, 'g', strSize);
uint32_t hval = rte_jhash(str, strSize, 0);
printf("Hash of %s (size %zu) is %u\n", str, strSize, hval);
free(str);
return 0;
}
ОБНОВЛЕНИЕ2: И вывод:
==27276==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60200000effc at pc 0x000000401315 bp 0x7ffdea936f80 sp 0x7ffdea936f70
READ of size 4 at 0x60200000effc thread T0
#0 0x401314 in __rte_jhash_2hashes /home/stefan/src/dpdk-17.08/x86_64-native-linuxapp-gcc/include/rte_jhash.h:165
#1 0x402771 in rte_jhash_2hashes /home/stefan/src/dpdk-17.08/x86_64-native-linuxapp-gcc/include/rte_jhash.h:266
#2 0x402830 in rte_jhash /home/stefan/src/dpdk-17.08/x86_64-native-linuxapp-gcc/include/rte_jhash.h:309
#3 0x4028e7 in main /home/stefan/src/test/misc/jhash_malloc.c:12
#4 0x7f470cb1f82f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
#5 0x400978 in _start (/home/stefan/src/test/misc/jhash_malloc+0x400978)
0x60200000effd is located 0 bytes to the right of 13-byte region [0x60200000eff0,0x60200000effd)
UPDATE3: исходный хеш-код Дженкинса выглядит так: http://burtleburtle.net/bob/c/lookup3.c. В источнике есть интересный комментарий, который предполагает, что предупреждение asan/valgrind можно игнорировать:
* "k[2]&0xffffff" actually reads beyond the end of the string, but
* then masks off the part it's not allowed to read. Because the
* string is aligned, the masked-off tail is in the same word as the
* rest of the string. Every machine with memory protection I've seen
* does it on word boundaries, so is OK with this. But VALGRIND will
* still catch it and complain. The masking trick does make the hash
* noticably faster for short strings (like English words).
Конечно, если вы хотите хешировать части более крупного объекта, для которого используется malloc, у вас все равно могут возникнуть проблемы.