Does malloc work?

[Zioo]

Allright im trying to write a malloc & free function. This i maybe a silly question, but how can I check that the malloc function actually works? Just beacuse it doesn't report errors, I can't be sure that it works. So how do I make a kind of check function?

[Solar]

Uh... same way as with any other function - adding debug output?

[Zioo]

Yes of course, but I would linke to have a kind of check function. It's because i'm still not 100% sure that i've understood how to write the function correct, and whats worse is that i don't know how to debug it.. ???

[Solar]

Insufficient input.

What do you want your check function to achieve?

You could, for example, do the following: If e.g. malloc( 100 ) is called, reserve 108 bytes. Write some magic number (e.g. 0xdeadbeef) at offset 0 and offset 104. Return a pointer to offset 4.

You now have a memory area of the requested 100 bytes, and you can check whether the words at offset -4 and offset 100 of what malloc() returned contain the magic number.

As for what malloc() should do and how to implement it... google for dlmalloc() (or look it up in the FAQ). It comes with a page that explains quite a lot about what a decent malloc() does internally.

[Zioo]

Allright.. My pagedirectory i setup at 0x200000 and the table at 0x201000..

If I do something ? la

Code: Select all

unsigned int *test = (unsigned int *)malloc(100);
vsprintf("Int: %i\n",test);

To times in row it prints 2097164 first time and 2097276 2nd time.. And if i instert free(test); between these to lines does it return 2097164 every time..

Isn't that correct? Or is my function broken?

[Candy]

Allright.. My pagedirectory i setup at 0x200000 and the table at 0x201000..

If I do something ? la

Code: Select all

unsigned int *test = (unsigned int *)malloc(100);
vsprintf("Int: %i\n",test);

To times in row it prints 2097164 first time and 2097276 2nd time.. And if i instert free(test); between these to lines does it return 2097164 every time..

Isn't that correct? Or is my function broken?

From what I can figure, that's 12 bytes beyond the start (sue me for knowing 2^21 like that, it's 2097152) of the allocatable area. Do you include a 4-byte start&4-byte end or a 12-byte start? If the second, it's fine. If the first, you probably allocate a 0-byte bit before the first block, which is not good.

[Pype.Clicker]

A memory allocator is something complicated to check. The first check you could do is trying to request e.g. 64K chunks as many times as possible until the system says there's no memory left and *then* release it. With simple computation, you should be able to tell whether it worked properly or not.

For the rest, it will depend on how you implemented stuff. HAve your code printed, and build a test case for each "branch" of it. For instance, if your allocator should be able to merge freed regions to make a contiguous new region, you could try:

Code: Select all

void *x=malloc(65536);
void *y=malloc(65536);
void *z=malloc(65536);

free(x); 
free(z);
free(y); // should merge those 3 zones in a new one.

now, that all depends on the algorithm you're being using. Your malloc could very well not satisfy x == y if you're running

Code: Select all

x=malloc(SIZE);
free(x);
y=malloc(SIZE);

and still operate as expected (that is, find and return available blocks as long as there are some, return errors if no memory is left and only if there's no more memory and never allocate twice the same byte).

[OZ]

depending on how you implemented your memory manager you could (if you use linked lists to manage the chunks of mem allocated/ etc.) print that list.
meaning something like:

block 1 [start address] [ size ] [ next address ]
...

Depending on your system to add an information header to the mem blocks the 'next address' will be 'start address' + size + size of your header. Therefore it should be the same as the start address of block 2.
By this you could at first check whether your manager writes over mem blocks it has assigned before.
If your list can't be walked properly there should definetly be a flaw in the code.

Next level could be implement a list with your new alloc function and test if that list works aswell and the addresses are valid.

at least for me this worked, but even if your satisfied with your mem manager you might realize one day that your basic paging code does not what you thought it did ... ;D
hope it helps

[Zioo]

Now have i tried a bit of anything.

If I run malloc(65536); more than 31 times my system crash. But if i run free(...) right after the malloc function does it never crash.

I've also tried OZ' solution and that gives me:

Code: Select all

MEM: StartHeap = 2097152 Size = 65535 EndHeap = 2162700
MEM: StartHeap = 2162700 Size = 65535 EndHeap = 2228248
MEM: StartHeap = 2228248 Size = 65535 EndHeap = 2293796

So I think it's working.. right?

[Pype.Clicker]

no, i fear not. The system shouldn't crash when malloc is out of memory. It should gracefully report that there's no more memory. period. E.g. if your system needs memory for a thread structure and that there's no more suitable memory, then the thread creation should be cancelled, but what's running should remain running.

[Zioo]

No it shouldn't crash, that will be fixed soon, but except from that?

[Solar]

Oh Zioo, come on. Debugging 101, anyone?

Make a list of everything that could go wrong:

• malloc() returning a pointer that isn't the correct offset into the area malloc() reserved internally.
• free() not really freeing all the memory allocated by malloc().
• malloc() misbehaving with very small chunks.
• malloc() misbehaving with very large chunks.
• malloc() misbehaving when multiple threads request memory.
• malloc() misbehaving when system memory runs low.
• ...

Just from the top of my head. I'm sure you can make a much longer list.

Then ask yourself, how can I know that these things don't happen? How can I make sure? How would I have to set up a test to check for that condition? Can it be automatted so I can run all tests I ever devised with a simple "make test"?

Only if you can no longer think of any marginal condition you haven't tested, mark your malloc() as beta and let your testers come up with a list of about 42 other conditions you never thought of but which make your malloc() crash.

[Warrior]

Yea..it's sorta impossible to find ALL the bugs in code (I wish it were possible though), best thing to do is fix them as you encounter them.

[Pype.Clicker]

Yea..it's sorta impossible to find ALL the bugs in code (I wish it were possible though), best thing to do is fix them as you encounter them.

::)

guys, have you ever heard of assert(), invariants, postconditions and other 'design by contract' stuff ? we (on the other side of MT) cannot give you an exhaustive list of test cases for your code because we do not *know* your code. You do. So you can create that exhaustive list of tests.

For instance, if you have your allocator initialized with a region of memory it will work on (lomem..himem), you can quite easily create a test function that will check any pointer returned by the allocator is within that region, or it's null. That's a postcondition.

You also know that (for instance) your free cells are organized as a linked list, so you could run a test after each allocation that ensures the list is still simply linked, that it doesn't contain loops, etc.
If used cells are in another list you can also write a test that checks the used stuff and that ensure that every byte in lomem...himem is listed by one of those cells, and exactly one.
This actually is an invariant condition: it should be true before any call, after every call and at every "major step" of your code.

So you certainly cannot grab *all* misbehaviours with that, but you can come with something that is fairly better than just writing code and "hum, that should work".

[Warrior]

Yea I've heard of it. It may help find some sure