Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why malloc always does more than I asked for?

ssenthilnathan3.github.io

Post reply on HN
Print view View original

11–20 of 52 posts

Re: Why malloc always does more than I asked for?

#11

Post by CodesInChaos »

phire wrote: post #8

> so alloc() doesn’t just need to hand back a pointer. it needs to hand back a pointer that’s correctly aligned for whatever type the caller is about to store there. Malloc doesn't know the required alignment (because has no idea what the type is, everything is cast through void ). So all malloc implementations have a minimum alignment guarantee. Typically 16 bytes these days on x86, as that means even 128bit SSE val…

There is no reason an allocation needs to contain any inline metadata. And even if it does, the allocator could choose to make it unalined, and pay the cost of an unalined access on de-allocation.

Re: Why malloc always does more than I asked for?

#12

Post by CodesInChaos »

Your bump allocator suffers from integer overflows turned into buffer overflows when the requested allocation is big enough:

  if (a->cursor + size > a->limit) return NULL; // out of memory
I'd rewrite it like this:

  if (size > a->limit - a->cursor) return NULL; // out of memory

Re: Why malloc always does more than I asked for?

#13

Post by phire »

CodesInChaos wrote: post #11
phire wrote: post #8

> so alloc() doesn’t just need to hand back a pointer. it needs to hand back a pointer that’s correctly aligned for whatever type the caller is about to store there. Malloc doesn't know the required alignment (because has no idea what the type is, everything is cast through void ). So all malloc implementations have a minimum alignment guarantee. Typically 16 bytes these days on x86, as that means even 128bit SSE val…

There is no reason an allocation needs to contain any inline metadata. And even if it does, the allocator could choose to make it unalined, and pay the cost of an unalined access on de-allocation.

True.

But most C code out there assumes malloc will always return something that is at least aligned to sizeof(void *), it's very rare to see aligned_alloc. So how is your alloc allocation going to know when it can get away with a smaller alignment?

Even if you are on a cpu that doesn't fault on unaligned memory access, any malloc implementation that doesn't align by default will have serious disadvantages in any benchmarks. IMO, There is no good reason to use an unaligned backpointer.

Re: Why malloc always does more than I asked for?

#14

Post by lexicality »

I'm a little confused. We start with

  [ Header ][ ...variable padding... ][ Back Pointer ][ User Memory ]
                                       ^ always exactly sizeof(void*)
                                         bytes before User Memory,
                                         no matter how much padding
                                         came before it
and then it says we don't need to align the back pointer and we end up with

  [ Header ][ Back Pointer ][ Padding ][ User Memory ]
without a clear explanation of how we now get to the back pointer if it's behind the variable alignment.

Re: Why malloc always does more than I asked for?

#15

Post by torh »

lexicality wrote: post #14

I'm a little confused. We start with [ Header ][ ...variable padding... ][ Back Pointer ][ User Memory ] ^ always exactly sizeof(void*) bytes before User Memory, no matter how much padding came before it and then it says we don't need to align the back pointer and we end up with [ Header ][ Back Pointer ][ Padding ][ User Memory ] without a clear explanation of how we now get to the back pointer if it's behind the va…

This puzzled me as well.

Re: Why malloc always does more than I asked for?

#16

Post by dn3500 »

CodesInChaos wrote: post #12

Your bump allocator suffers from integer overflows turned into buffer overflows when the requested allocation is big enough: if (a->cursor + size > a->limit) return NULL; // out of memory I'd rewrite it like this: if (size > a->limit - a->cursor) return NULL; // out of memory

Your test is backwards. I would write it like this:

  if (size > a->limit - a->cursor) return NULL;

Re: Why malloc always does more than I asked for?

#18

Post by CodesInChaos »

phire wrote: post #13
CodesInChaos wrote: post #11

Earlier quoted context omitted.

There is no reason an allocation needs to contain any inline metadata. And even if it does, the allocator could choose to make it unalined, and pay the cost of an unalined access on de-allocation.

True. But most C code out there assumes malloc will always return something that is at least aligned to sizeof(void *), it's very rare to see aligned_alloc. So how is your alloc allocation going to know when it can get away with a smaller alignment? Even if you are on a cpu that doesn't fault on unaligned memory access, any malloc implementation that doesn't align by default will have serious disadvantages in any ben…

Yes, large allocations need to be aligned to `alignof(max_align_t)`. But small allocations could have a smaller alignment. For example a single byte allocation can actually be a single byte with no alignment, since types can't have an alignment larger than their size.

Re: Why malloc always does more than I asked for?

#19

Post by CodesInChaos »

dn3500 wrote: post #16
CodesInChaos wrote: post #12

Your bump allocator suffers from integer overflows turned into buffer overflows when the requested allocation is big enough: if (a->cursor + size > a->limit) return NULL; // out of memory I'd rewrite it like this: if (size > a->limit - a->cursor) return NULL; // out of memory

Your test is backwards. I would write it like this: if (size > a->limit - a->cursor) return NULL;

You're right. Fixed.

Re: Why malloc always does more than I asked for?

#20

Post by xxs »

geocar wrote: post #6
irenaeus wrote: post #2

I've read some allocator walkthroughs before but I thought that this line stood out: "to get individual free() working, the allocator needs to remember something about every allocation it handed out. and that’s the moment metadata stops being optional." That's just a very nice distillation of an important concept.

Oh? How do you think munmap does it? If you can convince the caller to keep track of that metadata themselves you obviously don’t need to. That can be important. Something I noticed is that _very often_ the code that is calling malloc(n) is keeping track of n somehow for its own reasons (bounds checking, grow/gap pointers, etc) so merging the value halves stack churn and it’s an easy win.

> keep track of that metadata themselves you obviously don’t need to

likely it'd a be perf. hit in most cases. They'd have to copy to the tail end (likely) of the allocated area. Or the start and offset the pointer, they'd need to know the size of the metadata and account for that, including aligning it.Hence, the tail feels 'nicer'

It's possible to manually use mmap and forgo malloc entirely, rolling your own arena manager.

Post reply on HN