Add padding around allocation debugger structures
Commit Message
Architectures with a special alignment for load and store operations on
datatypes bigger than bytes will return a prealigned memory region when
calling malloc. When we add our data structure before and after this
region we destroy this alignment.
To fix this problem we add special regions with "magic" padding data.
To be sure that it is big enough for every load/store operation we use
the alignment for uintmax_t or a pointer even when the architecture only
supports smaller load/store operations.
Signed-off-by: Sven Eckelmann <sven.eckelmann@gmx.de>
---
batman/allocate.c | 77 +++++++++++++++++++++++++++++++++++++++++++++++-----
1 files changed, 69 insertions(+), 8 deletions(-)
Comments
On Thursday 28 May 2009 18:40:08 Sven Eckelmann wrote:
> Architectures with a special alignment for load and store operations on
> datatypes bigger than bytes will return a prealigned memory region when
> calling malloc. When we add our data structure before and after this
> region we destroy this alignment.
> To fix this problem we add special regions with "magic" padding data.
> To be sure that it is big enough for every load/store operation we use
> the alignment for uintmax_t or a pointer even when the architecture only
> supports smaller load/store operations.
>
> Signed-off-by: Sven Eckelmann <sven.eckelmann@gmx.de>
@Nathan: Could you let me know if these patches work for you ? If so I'll
commit them.
Regards,
Marek
On Fri, May 29, 2009 at 2:02 AM, Marek Lindner <lindner_marek@yahoo.de> wrote:
> On Thursday 28 May 2009 18:40:08 Sven Eckelmann wrote:
>> Architectures with a special alignment for load and store operations on
>> datatypes bigger than bytes will return a prealigned memory region when
>> calling malloc. When we add our data structure before and after this
>> region we destroy this alignment.
>> To fix this problem we add special regions with "magic" padding data.
>> To be sure that it is big enough for every load/store operation we use
>> the alignment for uintmax_t or a pointer even when the architecture only
>> supports smaller load/store operations.
>>
>> Signed-off-by: Sven Eckelmann <sven.eckelmann@gmx.de>
>
> @Nathan: Could you let me know if these patches work for you ? If so I'll
> commit them.
>
> Regards,
> Marek
>
>
I set /proc/cpu/alignment to 4 (raise bus error) and I get a bus error:
Program received signal SIGBUS, Bus error.
list_add_tail (new=0x29368, head=0x28819) at list-batman.c:68
68 __list_add( new, head->prev, (struct list_head *)head );
(gdb) l
63 * Insert a new entry before the specified head.
64 * This is useful for implementing queues.
65 */
66 void list_add_tail( struct list_head *new, struct
list_head_first *head ) {
67
68 __list_add( new, head->prev, (struct list_head *)head );
69
70 head->prev = new;
71
72 }
On Friday 29 May 2009 16:00:40 Nathan Wharton wrote:
> > @Nathan: Could you let me know if these patches work for you ? If so I'll
> > commit them.
> >
> > Regards,
> > Marek
>
> I set /proc/cpu/alignment to 4 (raise bus error) and I get a bus error:
>
> Program received signal SIGBUS, Bus error.
> list_add_tail (new=0x29368, head=0x28819) at list-batman.c:68
> 68 __list_add( new, head->prev, (struct list_head *)head );
> (gdb) l
> 63 * Insert a new entry before the specified head.
> 64 * This is useful for implementing queues.
> 65 */
> 66 void list_add_tail( struct list_head *new, struct
> list_head_first *head ) {
> 67
> 68 __list_add( new, head->prev, (struct list_head *)head );
> 69
> 70 head->prev = new;
> 71
> 72 }
Have you added the patches per hand? At this moment no patch I've made
available in trunk. As you have run it with gdb, can you please append a full
backtrace?
Best regards,
Sven
On Mon, Jun 1, 2009 at 11:44 AM, Sven Eckelmann <sven.eckelmann@gmx.de> wrote:
> On Friday 29 May 2009 16:00:40 Nathan Wharton wrote:
>> > @Nathan: Could you let me know if these patches work for you ? If so I'll
>> > commit them.
>> >
>> > Regards,
>> > Marek
>>
>> I set /proc/cpu/alignment to 4 (raise bus error) and I get a bus error:
>>
>> Program received signal SIGBUS, Bus error.
>> list_add_tail (new=0x29368, head=0x28819) at list-batman.c:68
>> 68 __list_add( new, head->prev, (struct list_head *)head );
>> (gdb) l
>> 63 * Insert a new entry before the specified head.
>> 64 * This is useful for implementing queues.
>> 65 */
>> 66 void list_add_tail( struct list_head *new, struct
>> list_head_first *head ) {
>> 67
>> 68 __list_add( new, head->prev, (struct list_head *)head );
>> 69
>> 70 head->prev = new;
>> 71
>> 72 }
> Have you added the patches per hand? At this moment no patch I've made
> available in trunk. As you have run it with gdb, can you please append a full
> backtrace?
>
> Best regards,
> Sven
>
I had to copy the patches out of the e-mail.
Here is the back trace:
#0 list_add_tail (new=0x29bf0, head=0x298c9) at list-batman.c:68
#1 0x0000ee7c in _hna_global_add (orig_node=0x29f80,
hna_element=0x29ba8) at hna.c:371
#2 0x0000f160 in hna_global_add (orig_node=0x29f80, new_hna=<value
optimized out>, new_hna_len=<value optimized out>)
at hna.c:529
#3 0x000099c8 in update_routes (orig_node=0x29f80,
neigh_node=0x2a080, hna_recv_buff=0xbead1591 "\n\002\001",
hna_buff_len=10) at batman.c:377
#4 0x0000c730 in update_orig (orig_node=0x29f80, in=0xbead157f,
neigh=167772673, if_incoming=0x27678,
hna_recv_buff=0xbead1591 "\n\002\001", hna_buff_len=-16723,
is_duplicate=0 '\0', curr_time=3199014207)
at originator.c:227
#5 0x0000a7e0 in batman () at batman.c:956
#6 0x000148d4 in main (argc=14, argv=0xbead1e14) at posix/posix.c:629
Looks like debugMalloc didn't return an aligned value for head. I'll
step through that and see what I see.
On Monday 01 June 2009 20:03:43 Nathan Wharton wrote:
> I had to copy the patches out of the e-mail.
>
> Here is the back trace:
> #0 list_add_tail (new=0x29bf0, head=0x298c9) at list-batman.c:68
> #1 0x0000ee7c in _hna_global_add (orig_node=0x29f80,
> hna_element=0x29ba8) at hna.c:371
> #2 0x0000f160 in hna_global_add (orig_node=0x29f80, new_hna=<value
> optimized out>, new_hna_len=<value optimized out>)
> at hna.c:529
> #3 0x000099c8 in update_routes (orig_node=0x29f80,
> neigh_node=0x2a080, hna_recv_buff=0xbead1591 "\n\002\001",
> hna_buff_len=10) at batman.c:377
> #4 0x0000c730 in update_orig (orig_node=0x29f80, in=0xbead157f,
> neigh=167772673, if_incoming=0x27678,
> hna_recv_buff=0xbead1591 "\n\002\001", hna_buff_len=-16723,
> is_duplicate=0 '\0', curr_time=3199014207)
> at originator.c:227
> #5 0x0000a7e0 in batman () at batman.c:956
> #6 0x000148d4 in main (argc=14, argv=0xbead1e14) at posix/posix.c:629
>
> Looks like debugMalloc didn't return an aligned value for head. I'll
> step through that and see what I see.
Ok, I think I see the problem. The malloc returned a valid aligned adress.
list_add_tail will get a pointer to an element in hna_global_entry. This
structure is packed and all operations on it should be non-alignment safe. If
you look at it further you will notice that orig_list is at position 9
(assuming 4 bytes for a pointer) - which will not be aligned to 4 bytes of
course.....
And here comes the problem: the compiler will only do the safe operations on
non-aligned data if it knows that it is not alignent. Since a cast is done by
calling list_add_tail it will not know that this parameter is not aligned and
the non-alignment bug will occur.
So my question to marek: Is it really needed to have "struct hna_global_entry"
packed in hna.h:57? If not then we should remove it and this problem should be
gone. And what is with "struct hna_element".
Thank you for your work, Nathan :)
Regards,
Sven
On Mon, Jun 1, 2009 at 2:35 PM, Sven Eckelmann <sven.eckelmann@gmx.de> wrote:
> Ok, I think I see the problem. The malloc returned a valid aligned adress.
> list_add_tail will get a pointer to an element in hna_global_entry. This
> structure is packed and all operations on it should be non-alignment safe. If
> you look at it further you will notice that orig_list is at position 9
> (assuming 4 bytes for a pointer) - which will not be aligned to 4 bytes of
> course.....
> And here comes the problem: the compiler will only do the safe operations on
> non-aligned data if it knows that it is not alignent. Since a cast is done by
> calling list_add_tail it will not know that this parameter is not aligned and
> the non-alignment bug will occur.
>
> So my question to marek: Is it really needed to have "struct hna_global_entry"
> packed in hna.h:57? If not then we should remove it and this problem should be
> gone. And what is with "struct hna_element".
>
> Thank you for your work, Nathan :)
You are welcome, thanks for your help.
The crashing of batgat on unloading turns out to be socket 4306 not
being ready to be reused yet.
I worked around this by using:
batmand -c -r 0 ; sleep 1 ; batmand -c -g 11000
and
batmand -c -g 0 ; sleep 1 ; batmand -c -r 2
Marek helped figure that out on irc.
On Tuesday 02 June 2009 03:35:07 Sven Eckelmann wrote:
> So my question to marek: Is it really needed to have "struct
> hna_global_entry" packed in hna.h:57? If not then we should remove it and
> this problem should be gone. And what is with "struct hna_element".
The first 5 bytes of both structs are used as base for the hash index. If the
compiler changes the order or something similar it might not work.
Regards,
Marek
On Tuesday 02 June 2009 06:36:41 Marek Lindner wrote:
> On Tuesday 02 June 2009 03:35:07 Sven Eckelmann wrote:
> > So my question to marek: Is it really needed to have "struct
> > hna_global_entry" packed in hna.h:57? If not then we should remove it and
> > this problem should be gone. And what is with "struct hna_element".
>
> The first 5 bytes of both structs are used as base for the hash index. If
> the compiler changes the order or something similar it might not work.
Ok, then it should be safe to force the alignment of the pointers in
hna_global_entry. Everything else seems to be much more complicated and
doesn't create much cleaner code.
Best regards,
Sven
@@ -67,6 +67,44 @@ struct memoryUsage
};
+static size_t getHeaderPad() {
+ size_t pad = sizeof(uintmax_t) - (sizeof(struct chunkHeader) % sizeof(uintmax_t));
+ if (pad == sizeof(uintmax_t))
+ return 0;
+ else
+ return pad;
+}
+
+static size_t getTrailerPad(size_t length) {
+ size_t pad = sizeof(uintmax_t) - (length % sizeof(uintmax_t));
+ if (pad == sizeof(uintmax_t))
+ return 0;
+ else
+ return pad;
+}
+
+static void fillPadding(unsigned char* padding, size_t length) {
+ unsigned char c = 0x00;
+ size_t i;
+
+ for (i = 0; i < length; i++) {
+ c += 0xA7;
+ padding[i] = c;
+ }
+}
+
+static int checkPadding(unsigned char* padding, size_t length) {
+ unsigned char c = 0x00;
+ size_t i;
+
+ for (i = 0; i < length; i++) {
+ c += 0xA7;
+ if (padding[i] != c)
+ return 0;
+ }
+ return 1;
+}
+
static void addMemory( uint32_t length, int32_t tag ) {
struct memoryUsage *walker;
@@ -176,7 +214,7 @@ void checkIntegrity(void)
memory = (unsigned char *)walker;
- chunkTrailer = (struct chunkTrailer *)(memory + sizeof(struct chunkHeader) + walker->length);
+ chunkTrailer = (struct chunkTrailer *)(memory + sizeof(struct chunkHeader) + getHeaderPad() + walker->length + getTrailerPad(walker->length));
if (chunkTrailer->magicNumber != MAGIC_NUMBER)
{
@@ -209,7 +247,7 @@ void *debugMalloc(uint32_t length, int32_t tag)
/* printf("sizeof(struct chunkHeader) = %u, sizeof (struct chunkTrailer) = %u\n", sizeof (struct chunkHeader), sizeof (struct chunkTrailer)); */
- memory = malloc(length + sizeof(struct chunkHeader) + sizeof(struct chunkTrailer));
+ memory = malloc(length + sizeof(struct chunkHeader) + sizeof(struct chunkTrailer) + getHeaderPad() + getTrailerPad(length));
if (memory == NULL)
{
@@ -218,8 +256,11 @@ void *debugMalloc(uint32_t length, int32_t tag)
}
chunkHeader = (struct chunkHeader *)memory;
- chunk = memory + sizeof(struct chunkHeader);
- chunkTrailer = (struct chunkTrailer *)(memory + sizeof(struct chunkHeader) + length);
+ chunk = memory + sizeof(struct chunkHeader) + getHeaderPad();
+ chunkTrailer = (struct chunkTrailer *)(memory + sizeof(struct chunkHeader) + length + getHeaderPad() + getTrailerPad(length));
+
+ fillPadding((unsigned char*)chunkHeader + sizeof(struct chunkHeader), getHeaderPad());
+ fillPadding(chunk + length, getTrailerPad(length));
chunkHeader->length = length;
chunkHeader->tag = tag;
@@ -251,7 +292,7 @@ void *debugRealloc(void *memoryParameter, uint32_t length, int32_t tag)
if (memoryParameter) { /* if memoryParameter==NULL, realloc() should work like malloc() !! */
memory = memoryParameter;
- chunkHeader = (struct chunkHeader *)(memory - sizeof(struct chunkHeader));
+ chunkHeader = (struct chunkHeader *)(memory - sizeof(struct chunkHeader) - getHeaderPad());
if (chunkHeader->magicNumber != MAGIC_NUMBER)
{
@@ -259,13 +300,23 @@ void *debugRealloc(void *memoryParameter, uint32_t length, int32_t tag)
restore_and_exit(0);
}
- chunkTrailer = (struct chunkTrailer *)(memory + chunkHeader->length);
+ if (checkPadding(memory - getHeaderPad(), getHeaderPad()) == 0) {
+ debug_output( 0, "debugRealloc - invalid magic padding in header, malloc tag = %d\n", chunkHeader->tag );
+ restore_and_exit(0);
+ }
+
+ chunkTrailer = (struct chunkTrailer *)(memory + chunkHeader->length + getTrailerPad(chunkHeader->length));
if (chunkTrailer->magicNumber != MAGIC_NUMBER)
{
debug_output( 0, "debugRealloc - invalid magic number in trailer: %08x, malloc tag = %d\n", chunkTrailer->magicNumber, chunkHeader->tag );
restore_and_exit(0);
}
+
+ if (checkPadding(memory + chunkHeader->length, getTrailerPad(chunkHeader->length)) == 0) {
+ debug_output( 0, "debugRealloc - invalid magic padding in trailer, malloc tag = %d\n", chunkHeader->tag );
+ restore_and_exit(0);
+ }
}
@@ -292,7 +343,7 @@ void debugFree(void *memoryParameter, int tag)
struct chunkHeader *previous;
memory = memoryParameter;
- chunkHeader = (struct chunkHeader *)(memory - sizeof(struct chunkHeader));
+ chunkHeader = (struct chunkHeader *)(memory - sizeof(struct chunkHeader) - getHeaderPad());
if (chunkHeader->magicNumber != MAGIC_NUMBER)
{
@@ -300,6 +351,11 @@ void debugFree(void *memoryParameter, int tag)
restore_and_exit(0);
}
+ if (checkPadding(memory - getHeaderPad(), getHeaderPad()) == 0) {
+ debug_output( 0, "debugFree - invalid magic padding in header, malloc tag = %d\n", chunkHeader->tag );
+ restore_and_exit(0);
+ }
+
previous = NULL;
pthread_mutex_lock(&chunk_mutex);
@@ -326,7 +382,7 @@ void debugFree(void *memoryParameter, int tag)
pthread_mutex_unlock(&chunk_mutex);
- chunkTrailer = (struct chunkTrailer *)(memory + chunkHeader->length);
+ chunkTrailer = (struct chunkTrailer *)(memory + chunkHeader->length + getTrailerPad(chunkHeader->length));
if (chunkTrailer->magicNumber != MAGIC_NUMBER)
{
@@ -334,6 +390,11 @@ void debugFree(void *memoryParameter, int tag)
restore_and_exit(0);
}
+ if (checkPadding(memory + chunkHeader->length, getTrailerPad(chunkHeader->length)) == 0) {
+ debug_output( 0, "debugFree - invalid magic padding in trailer, malloc tag = %d\n", chunkHeader->tag );
+ restore_and_exit(0);
+ }
+
#if defined MEMORY_USAGE
removeMemory( chunkHeader->tag, tag );