OpenSolaris邮件列表中关于malloc实现的讨论

转载自：OpenSolaris: code

dmazeska        

Posts: 2
Registered: 6/29/05
    
Unread     Malloc overview
Posted: Jun 30, 2005 4:08 AM     
      Click to reply to this thread     Reply

Does anyone know of any good sites that offer a description of how the default Solaris malloc routine works?

I looked at the code for malloc.c but couldn't quite figure some things out.

It seems that data that is malloc'ed with less than 20 bytes will have added overhead of 8 bytes. I see 4 bytes for the size but I don't understand what the other 4 bytes are needed for. It seems very wasteful to me but I have to assume those extra 4 bytes must be there for a reason.

Data malloced over 20 bytes seems to have memory overhead of 24 bytes as the address returned is stored in a TREE pointer. I guess the way this memory allocation tree works is what's confusing me the most and was hoping someone had a good write up for how it works.

Thanks in advance.

barts     

Posts: 11
From: Menlo Park, CA
Registered: 3/21/05
    
Unread     Re: Malloc overview
Posted: Jun 30, 2005 6:01 AM   in response to: dmazeska in response to: dmazeska     
      Click to reply to this thread     Reply

David Mazeska wrote:
> Does anyone know of any good sites that offer a description of how the default Solaris malloc routine works?
>

Other than the source, I don't know of one.

http://cvs.opensolaris.org/source/xref/usr/src/lib/libc/port/gen/malloc.c
http://cvs.opensolaris.org/source/xref/usr/src/lib/libc/port/gen/malllint.h

I'm currently working on a revised version of this malloc that replaces the
-smalloc (small block) routines with a slab type allocator; this will use
a page hash table to keep track of which pages are used for small blocks so
as to avoid the 8 byte allocation overhead for small blocks.

> I looked at the code for malloc.c but couldn't quite figure some things out.
>
> It seems that data that is malloc'ed with less than 20 bytes will have added overhead of
> 8 bytes. I see 4 bytes for the size but I don't understand what the other 4 bytes are
> needed for. It seems very wasteful to me but I have to assume those extra 4 bytes must
> be there for a reason.
>
All allocations have 8 bytes of overhead, prepended in the usual way. 8 bytes are used since
the default alignment for 32 bit programs is 8 bytes; using 4 bytes would cause misalignment
problems.

> Data malloced over 20 bytes seems to have memory overhead of 24 bytes as the address
> returned is stored in a TREE pointer. I guess the way this memory allocation tree works
> is what's confusing me the most and was hoping someone had a good write up for how it works.

Actually, all blocks have just the 8 byte overhead. Frred blocks over a certain size (that can
hold a TREE structure) are kept on a balanced binary tree; small freed blocks are kept on
simple linked lists.... the logic for this is in realfree. Each freed block contains pointers
to the adjacent blocks... the next block address can be computed knowing the size, the
previous block address cannot be known w/o walking the tree, so freeing a block is marked
in the next blocks unused bit 1 of the size field...

I'm afraid the code is a bit subtle.... reviewing mallint.h and the code in realfree is a
really good place to start.



- Bart

--
Bart Smaalders Solaris Kernel Solaris Software
barts at cyber dot eng dot sun dot com (650) 786-5335 MS UMPK17-301
http://blogs.sun.com/barts

_______________________________________________
opensolaris-code mailing list
opensolaris-code at opensolaris dot org
https://opensolaris.org:444/mailman/listinfo/opensolaris-code



dmazeska     

Posts: 2
Registered: 6/29/05
    
Unread     Re: Malloc overview
Posted: Jun 30, 2005 11:06 PM   in response to: dmazeska in response to: dmazeska     
      Click to reply to this thread     Reply

Bart,
Thanks for the response. That helps alot. I guess I always figured default alignment would be 4 bytes for 32 bit code.

As a developer, its good to know malloc adds 8 bytes of overhead to each piece of memory allocated. I always suspected there was some overhead but I'm glad to know the actual number.

wesolows     

Posts: 77
From: Menlo Park CA US
Registered: 3/21/05
    
Unread     Re: Re: Malloc overview
Posted: Jul 1, 2005 12:18 AM   in response to: dmazeska in response to: dmazeska     
      Click to reply to this thread     Reply

On Thu, Jun 30, 2005 at 08:06:22AM -0700, David Mazeska wrote:

> Thanks for the response. That helps alot. I guess I always figured
> default alignment would be 4 bytes for 32 bit code.

Most architectures require data to be aligned to its size. That
includes doubles and long longs. If malloc returned 4-byte aligned
storage, those types, or structures containing them, could be
misaligned.

We found a number of places where local malloc implementations assumed
that 4-byte alignment was sufficient, but were used to allocate
structures containing long long types. This wasn't a problem when
compiled with Studio, because it doesn't seem to emit SPARC integer
ldd and std instructions for long long accesses (even with
-xmemalign=8s). gcc does, however, and these defective
implementations caused crashes. See for example 6268299. The
approach we're taking with these is a combination attack: fix the bugs
and, until we're confident we've found and fixed all such
implementations, tell gcc not to emit these instructions.

--
Keith M Wesolowski "Sir, we're surrounded!"
Solaris Kernel Team "Excellent; we can attack in any direction!"
_______________________________________________
opensolaris-code mailing list
opensolaris-code at opensolaris dot org
https://opensolaris.org:444/mailman/listinfo/opensolaris-code



barts     

Posts: 11
From: Menlo Park, CA
Registered: 3/21/05
    
Unread     Re: Re: Malloc overview
Posted: Jul 1, 2005 2:50 AM   in response to: dmazeska in response to: dmazeska     
      Click to reply to this thread     Reply

David Mazeska wrote:
> Bart,
> Thanks for the response. That helps alot. I guess I always figured default alignment would be 4 bytes for 32 bit code.
>
> As a developer, its good to know malloc adds 8 bytes of overhead to each piece of memory allocated. I always suspected there was some overhead but I'm glad to know the actual number.
> This message posted from opensolaris.org
> _______________________________________________
> opensolaris-code mailing list
> opensolaris-code at opensolaris dot org
> https://opensolaris.org:444/mailman/listinfo/opensolaris-code

The reason that 8 bytes are required is that malloc must return memory
aligned for any use (as long as the size of the block could contain such
an object). Since doubles can be required to be aligned to 8 byte boundaries,
malloc must return memory thusly aligned.


- Bart


--
Bart Smaalders Solaris Kernel Solaris Software
barts at cyber dot eng dot sun dot com (650) 786-5335 MS UMPK17-301
http://blogs.sun.com/barts

_______________________________________________
opensolaris-code mailing list
opensolaris-code at opensolaris dot org
https://opensolaris.org:444/mailman/listinfo/opensolaris-code

原文转自：http://www.ltesting.net