Paged malloc/free/realloc thorough test suite

[~]

I need a malloc test suite with examples to make sure I am covering any corner cases when managing memory.

Could you give me or point to malloc/realloc/free examples? I need to test that I can allocate/deallocate blocks in any fashion.

I've created a basic paged kernel-mode malloc function called OPCODE__klibc32__malloc_PG_0

You can see the function in the file
CPU/x86-32/paging/malloc_system/malloc.asm

You can read it here or run it under a pure DOS install:
https://sourceforge.net/projects/lowest ... p/download

[bzt]

Hi,

I think that would be highly malloc implementation specific. For example there's no need to check arena inconsistency with DLmalloc, but it is with jemalloc, there's a need to check free header block consistency with DLmalloc and useless with jemalloc, empty, unmerged slabs are only concern when using slab allocator ...etc.

Google for these: doug lea's malloc, jemalloc, ptmalloc, hoard, solaris slab for starters, their source repo usually has tests (however tuned for the edge cases of their allocator's algorithm's edge cases).

I think the only common test you could have is allocating N times M memory (see how much RAM it takes), then allocate one time N*M (see how much it takes), and if you free both then see if all memory truely freed (including allocator's meta data). I mean in general we can expect that an allocator wastes more RAM with allocating 100 times 10 bytes, and much less with allocating 1 time 1000 bytes. After freeing, we would expect to free that overhead as well (if it's not that could be an indicator that slab for example does not merge free neigbouring blocks). There's also a wasted memory (not used by the application or the allocator meta-data either) because most allocators use power of 2 units, meaning 100 x 10 bytes would allocate 100 x 16 bytes, wasting 600 bytes, on the other hand 1 time 1000 would waste 24 bytes only.

You can take a look at my ANSI C allocator bztalloc, although it is tuned for 64 bits, it should be straightforward to apply it to 32 bits by changing the ALLOCSIZE from 2M to 1M, and minimum quantum size from 8 bytes to 4 bytes. I've tried to find the balance between simplicity, performance, stability and portability. Writing an allocator is not an easy task at all, requires lot of research and clear vision how it should work. For example mine does not use sbrk, but asks for 4k pages and 2M blocks (1M with 32 bits) from the kernel using the POSIX mmap()/munmap() interface (feel free to change those calls with your kernel's interface).

Cheers,
bzt

[nullplan]

If you wish to test the interface, there is not a whole lot you can do. Check that realloc() works for p = 0 and for size = 0, check that malloc(0) does something sensible. Test that you can realloc a block obtained by malloc() or realloc(), and that you can access the whole new length of the array. free(), for instance, has no effect you can detect in general in C. If you made free() into a no-op, there is in general no way to tell. So you really have to write tests for your implementation.

A stress test you can do is multi-threaded malloc() performance. But even that would be better as implementation test, because then you could test for heap corruption.

[~]

Probably the best test suite will be developed over time based on real applications, then asking for better test cases.

Probably the most basic test case would be to malloc from a size of 0 check for errors, until allocating all with realloc, and back from N to 0 to see if there are no memory leaks.

The other test would be to test how many variables smaller than the physical block we can allocate in a program; how to realloc without failing for too much fragmentation.

[0xCC]

I'm trying to test my malloc too and here is some testes i came by:
- Allocate multiple pages and write to them different values, then check the values if they are the same as you set them before (this checks if the allocated pages has different memory frames with the right access)
- Allocate memory at some address then allocate other memory at same address and addresses below it with overlapping regions (this should return error since it's not possible for virtual memory to overlap)
- Allocate more than 4MB in address in a way that it takes to 2 page directory entries to be filled.
- Implement function to get used memory size by the used frames and monitor the size before and after some allocations.

[~]

The first thing is that if we know the desired virtual address, we don't need to iterate, only access the structure indexes indicated by such address.

Searching for DPMI tutorials and implementing the services with ours could be a great way to easily complete most functions we want.

sbrk...