OSDev.org

I am at the point where I need to write a malloc function. If I understand things correctly, most malloc implementations store information on free and allocated blocks of memory in a dynamically growing structure such as a linked list. What I don't understand is where to store these structures. Do most people simply designate some place in the virtual address space to store this information? Or is there a more clever solution?

Any advice would be appreciated
Thanks,
Justin

Unfortunately, there are an infinity of solutions. The one that I thought was the most clever (and that I am using) is to store the malloc list information in a tiny structure just before the beginning of the malloc'ed memory area. You allocate space for the list entry at the same time as you create the requested mem allocation.

So, for example, when a program issues a free(malloc_mem_ptr), all you have to do is say malloc_hdr_struct_ptr = malloc_mem_ptr - malloc_hdr_struct_size;
And then you have instant access to the list entry for that (formerly) malloc'ed area, so you can unlink it from the list.

This way, the programmer is free to completely trash his entire malloc list structure by accident. Some people (such as C++ programmers) say that it is the system's responsibility to protect programmers from themselves. I disagree completely -- which is one reason I chose this design.

bewing wrote:This way, the programmer is free to completely trash his entire malloc list structure by accident. Some people (such as C++ programmers) say that it is the system's responsibility to protect programmers from themselves. I disagree completely -- which is one reason I chose this design.

I'm a C++ programmer and I think you have a point . I do think the operating system needs at least some security of the memory, but not doing it is a way of making the programmer more aware of what he/she is doing. Some of today's programmers don't even care (in C/C++) about deleting/freeing their allocated memory anymore, as the 'OS will clean it up', but this is a good way to keep programmers alert.

But anyhow, if you don't have any protection and the programmer can easily mess something up. That also means malware can do it, which is not really the programmer's fault.

I guess it's how you look at it.

In a properly designed OS, no application can trash another application's address space. This is what makes an entire system safe from bad programmers and malware. But that rule says nothing about a program (including malware) trashing its own address space. Who cares if a badly written program crashes itself? Not me.

bewing wrote:In a properly designed OS, no application can trash another application's address space. This is what makes an entire system safe from bad programmers and malware. But that rule says nothing about a program (including malware) trashing its own address space. Who cares if a badly written program crashes itself? Not me.

Then what's the point of say, implementing support for monitors in a multithreaded OS? It's up to the application to handle its own affairs. I, as a programmer, if given the choice, would choose an OS with as much protection as possible.

bewing wrote:In a properly designed OS, no application can trash another application's address space. This is what makes an entire system safe from bad programmers and malware. But that rule says nothing about a program (including malware) trashing its own address space. Who cares if a badly written program crashes itself? Not me.

You have a good point there. I don't see why the OS should protect an application from itself, as long as it doesn't (try to) trash anything else in the OS, just let it crash on its own space and the OS will clean it up if needed for new applications afterwards.

Love4Boobies wrote:Then what's the point of say, implementing support for monitors in a multithreaded OS? It's up to the application to handle its own affairs. I, as a programmer, if given the choice, would choose an OS with as much protection as possible.

Then, would you rather switch to kernel mode and let the kernel allocate a chunk of memory for you each time you call malloc and related functions - and lose serious performance? Even if you did that, it would still not solve the problem of the application overwriting its own memory blocks.

bewing wrote:to store the malloc list information in a tiny structure just before the beginning of the malloc'ed memory area. (...) This way, the programmer is free to completely trash his entire malloc list structure by accident.

I use a slightly different approach, and have the free/occupied memory list at the top of the mallocable memory area (growing down). I think I copied that idea from Turbo Pascal, but I may be wrong. I just think it's very inelegant interleaving data and meta data, but that's just me I guess.


JAL