[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[bug-mailutils] Bug in hashtable implementation (mailbox/assoc.c)
From: |
Serge Monkewitz |
Subject: |
[bug-mailutils] Bug in hashtable implementation (mailbox/assoc.c) |
Date: |
Fri, 06 Feb 2009 18:19:53 -0800 |
User-agent: |
Opera Mail/9.61 (MacIntel) |
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
- [bug-mailutils] Bug in hashtable implementation (mailbox/assoc.c),
Serge Monkewitz <=