A quick tutorial on implementing C memory management functions
1–10 of 22 posts
Re: A quick tutorial on implementing C memory management functions
#2Great tutorial, Dan! Since it sounds like you are planning to continue the series, I have a few thoughts on potential directions to go with it.
First, a link to Doug Lea's classic malloc page might be a good addition to the resources section. His dlmalloc() is the basis for GCC's current ptmalloc. His code is wonderfully clear and commented, both for the implementation and the rationale behind it: http://g.oswego.edu/dl/html/malloc.html
Second, I wonder if it would make sense to jump straight to using mmap() instead of the classic brk()/sbrk(). I think it's no more complicated, has more uses elsewhere, is conceptually more portable, and allows multiple arena's to be added in a straightforward way. Are there advantages I'm not seeing to sticking to the ancient ways?
Last, on the debugging side, I think you might want to start with an introduction to Valgrind rather than gdb. It's a much easier learning curve, and even for an expert it's often the better tool for the memory allocation type bugs that are going to be most common here. Alternatively (or additionally) some examples of the more modern Address Sanitizer that's now in GCC and CLang would be slick: https://code.google.com/p/address-sanitizer/wiki/AddressSani...
Re: A quick tutorial on implementing C memory management functions
#3I have "a thing" for basic system services like malloc, linker, etc.
Writing a memory allocator is a nice exercise but it's also fundamental research: by toying around, because of sheer interest, with what everyone else takes for granted you might come up with something that changes things for all, big time.
For example, memory allocators were considered a "well enough solved" problem for a long time until suddenly we had a rush of new, experimental, and/or optimized allocators like jemalloc, tcmalloc etc. While they might not be revolutionary they still blast the old 80's/90's implementations like no tomorrow.
Re: A quick tutorial on implementing C memory management functions
#4There is a much better discussion of this in vol. I of Knuth.
(Amusingly, in the original edition Knuth uses a simple algorithm (linking the allocated spaces) in the text and leaves the better algorithm (linking the free spaces) to an exercise. In Unix V6 (yes, this really dates me), the "malloc" in the C library used the simple algorithm from Knuth, variable names and all, causing O(N^2) performance problems.)
Re: A quick tutorial on implementing C memory management functions
#5I have "a thing" for basic system services like malloc, linker, etc. Writing a memory allocator is a nice exercise but it's also fundamental research: by toying around, because of sheer interest, with what everyone else takes for granted you might come up with something that changes things for all, big time. For example, memory allocators were considered a "well enough solved" problem for a long time until suddenly w…
Linkers don't get as much attention as they should. The linker has the last chance to look at the entire program before it runs. It's a good place for final checks and optimizations.
In Modula, each module had an "init" section. The Modula linker traced the dependencies of the "init" sections and arranged for them to be executed in a valid order. If there was a dependency loop, that was an error. That's way ahead of the C/C++ rules on order of initialization.
Elimination of duplicate code at link time is possible. For template and generic instantiations, this can be a big win, especially for C++.
Some linkers support "weak links" - if A has a weak link to B, and there are no strong links to B, B is not loaded and the link is null. This is useful for optional components which need some kind of startup.
Re: A quick tutorial on implementing C memory management functions
#6Great tutorial, Dan! Since it sounds like you are planning to continue the series, I have a few thoughts on potential directions to go with it. First, a link to Doug Lea's classic malloc page might be a good addition to the resources section. His dlmalloc() is the basis for GCC's current ptmalloc. His code is wonderfully clear and commented, both for the implementation and the rationale behind it: http://g.oswego.edu…
> Second, I wonder if it would make sense to jump straight to using mmap() instead of the classic brk()/sbrk().
Yes, it will. brk/sbrk are terrible ways to allocate anything but more stack. Use mmap instead, both for more control over the layout in memory, and for more portability.
Re: A quick tutorial on implementing C memory management functions
#7The HN title doesn't match the article title "A Quick Tutorial on Implementing and Debugging Malloc, Free, Calloc, and Realloc" but from the article it is obviously C.
The mentioning of sbrk in the article seems to do so in passing. Nothing describes what it is. I would spend time on it.
I would also address virtual memory and at least let the reader know that the underlying operating system is ultimately responsible for allocating memory. When a modern OS uses virtual memory, you get a virtual memory pointer which would be different than the physical address.
Linux, in particular, uses a process referred to as Optimistic Memory Allocation to honor malloc requests.
I mention all this because I think anyone interested in these lower level details would also be interested in how the OS and hardware are involved.
Re: A quick tutorial on implementing C memory management functions
#8Great tutorial, Dan! Since it sounds like you are planning to continue the series, I have a few thoughts on potential directions to go with it. First, a link to Doug Lea's classic malloc page might be a good addition to the resources section. His dlmalloc() is the basis for GCC's current ptmalloc. His code is wonderfully clear and commented, both for the implementation and the rationale behind it: http://g.oswego.edu…
> Second, I wonder if it would make sense to jump straight to using mmap() instead of the classic brk()/sbrk(). Yes, it will. brk/sbrk are terrible ways to allocate anything but more stack. Use mmap instead, both for more control over the layout in memory, and for more portability.
[deleted]
Re: A quick tutorial on implementing C memory management functions
#9Great tutorial, Dan! Since it sounds like you are planning to continue the series, I have a few thoughts on potential directions to go with it. First, a link to Doug Lea's classic malloc page might be a good addition to the resources section. His dlmalloc() is the basis for GCC's current ptmalloc. His code is wonderfully clear and commented, both for the implementation and the rationale behind it: http://g.oswego.edu…
> Second, I wonder if it would make sense to jump straight to using mmap() instead of the classic brk()/sbrk(). Yes, it will. brk/sbrk are terrible ways to allocate anything but more stack. Use mmap instead, both for more control over the layout in memory, and for more portability.
Perhaps you know: on Linux, how do mmap() and brk() differ as far as page initialization? Does brk() conceptually include the effects of MAP_POPULATE? Do both of them cause virtual to physical memory mapping at the time of the call?
Re: A quick tutorial on implementing C memory management functions
#10Earlier quoted context omitted.
> Second, I wonder if it would make sense to jump straight to using mmap() instead of the classic brk()/sbrk(). Yes, it will. brk/sbrk are terrible ways to allocate anything but more stack. Use mmap instead, both for more control over the layout in memory, and for more portability.
Perhaps you know: on Linux, how do mmap() and brk() differ as far as page initialization? Does brk() conceptually include the effects of MAP_POPULATE? Do both of them cause virtual to physical memory mapping at the time of the call?
I'm not sure as to the specifics, because brk is a strict subset of mmap; however, I would be surprised if it doesn't use the full VM substructure to allocate the mapping immediately.
I would amend my statement before to say that, if you're looking into memory allocation, conceptually, mmap is where everything happens these days. brk is kept for backwards compatibility.