-1

Possible Duplicate:
Code for malloc and free

If not, can somebody explain to me how malloc() works (what algorithms/data structures it uses). I want to compare the standard library's implementation with my own implementation of malloc().

Community
  • 1
  • 1
David
  • 83
  • 2
  • 8

4 Answers4

3

Gnu source code

Tio Pepe
  • 3,071
  • 1
  • 17
  • 22
1

there are many implementations: http://freebsd.active-venture.com/FreeBSD-srctree/newsrc/i386/boot/cdboot/malloc.c.html

http://www.google.co.uk/search?q=malloc+source+code

Charbel
  • 14,187
  • 12
  • 44
  • 66
1

The canonical implementation is dlmalloc:

http://g.oswego.edu/dl/html/malloc.html

Any implementation that's not pure junk uses the same basic bin algorithms, but may have things like thread-local caches, arenas, etc. that might help performance but make it a lot harder to understand, so I would just read dlmalloc and save the rest for when you feel like making yourself suffer. As a major plus, dlmalloc's algorithms are very well-documented; see the link I provided.

R.. GitHub STOP HELPING ICE
  • 208,859
  • 35
  • 376
  • 711
0

The standard library functions are implemented per platform, so the implementation for any given platform may take any of several approaches. Terms to search for include: fixed block allocators, buddy block allocators, slab allocators etc.

Vicky
  • 12,934
  • 4
  • 46
  • 54
  • The types of allocators you cited are all known to be very bad... :-) – R.. GitHub STOP HELPING ICE Oct 21 '11 at 09:51
  • @R..: They've all got their pros and cons! If the OP has implemented his own without reference to any others (based on the fact he's now looking for example source code) then it's probably one of the simpler types he's created. – Vicky Oct 21 '11 at 10:11
  • Well, at least you're halfway right - they've all got their cons. Compared to the standard dlmalloc algorithm, they don't have any pros... Personally I consider teaching (much less using) the buddy block allocator roughly equivalent to teaching bubble sort. Like bubble sort, it's not intuitive, and like bubble sort, it's worse than all the alternatives in all possible ways. – R.. GitHub STOP HELPING ICE Oct 21 '11 at 11:47
  • 1
    OK, we'll have to agree to disagree there then. I think naive algorithms like buddy block or bubble sort have a very valuable place in teaching / learning about the options. – Vicky Oct 21 '11 at 14:17
  • I think naive algorithms have a very important place in teaching, but I don't see either of those as naive. Insertion sort is naive and a very natural choice for someone who doesn't know anything better - actually the first sort I ever wrote (in BASIC) was an insertion sort. Bubble sort you have to think about, then you wonder why anybody came up with something so awkward. For me, a "naive" allocator would use a free list and adjacent free block merging. The only major conceptual step past that for getting to dlmalloc is realizing that you can make separate lists segregated by size. – R.. GitHub STOP HELPING ICE Oct 21 '11 at 19:41