[bug-mailutils] Bug in hashtable implementation (mailbox/assoc.c)

[Serge Monkewitz]

In mailbox/assoc.c of mailutils-2.0, on lines 61 and onwards there's code  
that looks like this:

#define ASSOC_ELEM_SIZE(a) ((a)->elsize + sizeof(struct _mu_assoc_elem) -  
1)

#define __ASSOC_ELEM(a,p,n) \
 ((struct _mu_assoc_elem*) ((char*) (p) + ASSOC_ELEM_SIZE (a) * n))

#define ASSOC_ELEM(a,n) __ASSOC_ELEM(a,(a)->tab,n)

#define ASSOC_ELEM_INDEX(a,e) \
 (((char*)(e) - (char*)(a)->tab) / ASSOC_ELEM_SIZE (a))

On my Solaris 9 SPARC box, I'm seeing a bus error inside mu_assoc_clear()  
(line 256 of assoc.c):

if (elem->name)

where the elem pointer is a struct _mu_assoc_elem * obtained via the  
ASSOC_ELEM() macro. As far as I can tell, this is because ASSOC_ELEM_SIZE  
doesn't take structure alignment into account. On my box, sizeof(struct  
_mu_assoc_elem) is 8, and elsize for the hashtable that's causing the bus  
error is 4, which makes ASSOC_ELEM_SIZE() 11. Now ASSOC_ELEM_SIZE is used  
to index into the array underlying the hash table implementation, so the  
code places struct _mu_assoc_elem instances at addresses with arbitrary  
alignment. Therefore, the elem->name memory access above is unaligned,  
which on some platforms (including mine) causes a bus-error.

If I replace the ASSOC_ELEM_SIZE() macro with the following:

#define __ASSOC_ELEM_ALIGNOF offsetof(struct { char c; struct  
_mu_assoc_elem x; }, x)
#define __ASSOC_ELEM_SIZE(a) ((a)->elsize + offsetof(struct  
_mu_assoc_elem, data))
#define __ASSOC_ALIGN(a, b)  ((a + b - 1) & ~(b - 1))

#define ASSOC_ELEM_SIZE(a) __ASSOC_ALIGN(__ASSOC_ELEM_SIZE(a),  
__ASSOC_ELEM_ALIGNOF)

then the bus error goes away. Note that the __ASSOC_ALIGN macro assumes  
that b (__ASSOC_ELEM_ALIGNOF) is a power of 2. Also, the amount of memory  
used per hash table element actually goes down: when elsize <= sizeof(char  
*), then ASSOC_ELEM_SIZE will just be sizeof(struct _mu_assoc_elem) on  
most platforms. Furthermore, on platforms that allow unaligned memory  
access, aligned accesses may yield performance wins.

Regards,
Serge