As (typedef I think it was) said a very long time, I should ask for a project after I learn a few things.

Well, I think it's that time. I mean, I made the PerformanceCounter macro, but I'm kinda lost now. I have no project and the only thing that is on my mind (making a memory allocator) is far too advanced for me.

So I'm asking, is there anyone out here who would have something challenging (but not impossible), that would make me learn new things? Force me to think more in assembly? I'd be grateful if someone took the time to think up a challenge. My skill is still weak, so take it easy on me, please.

A memory allocator is only as advanced as you make it. You can make a simple heap with only tens of lines of code.

Well the trouble is, where to begin? How do I actually allocate memory? Some people say you do it by syscall, but others say you do it by HeapAlloc and should never touch syscall unless you're writing an OS or driver. I have attempted to dissect code of two memory allocators in C and for the life of me I can't find the part that actually does the allocation

In Windows the fastest thing I know is VirtualAlloc, VirtualFree function.

You appear to be mixing Linux syscalls with Windows APIs there. If you want to use the C HLL library functions for memory allocation then you have somewhat made the whole discussion moot. For assembly you would most likely want to use the OS provided functions (that is what C uses internally of course) to allocate memory for your app. There really isn't any other way to do it since the OS will have control over what you can and can't do. It is not about fastest here. The Virtual* functions have a particular purpose where their use makes sense. And the Heap* functions have a different purpose where their use makes sense. The Local* functions have their particular purpose also. You have to look at what your app needs to decide what is the right set of functions to use.

I see. I'll try to create something and then ask some specific questions instead.

I coded a few heaps for Windows, so I can provide some advice.
Basically, you use Win32 VirtualAlloc to allocate large segments of memory (say, 8Mb per segment).
Then to allocate small blocks (like 22 bytes for some string or a small structure) you cut the piece (22 byte piece) of that big block and return its address to the caller. Once the segment is ended -- call VirtualAlloc to get a fresh one.
When memory is freed -- try to see if the released block has free neighbouring block(s) and make a larger block from these.

The rest is optimization. Always keep the pointer to next free block, so
you perform less searching for a block.

Write a function to defragment all segments in heap.

And of course, diagnostics are very important:
- detect memory leaks
- detect when a block passed to free()/realloc() is invalid
- detect the memory block overrun

Maybe, when creating a heap object -- use some parameter to switch
diagnostics ON/OFF, because diagnostics will slow down your code considerably.

The memory block structure in memory can look like that:

These structures are following each other within a segment.
BLK_HEAD is a structure, containing the size of a block, flags (like is the block free or allocated) and in case of diagnostics -- some tag, which indicates that this is indeed the valid block.

BLK_TAIL is optional and usually (in case diagnostics are ON) contains the bytes to detect if a block has been damaged or overwritten.

The memory returned from your allocator should be aligned to 8 bytes to comply with the data alignment requirements. It may not, but then most of CPUs will slow down the code, which works with allocated data.

Example, the block of 22 bytes must be allocated.
It means the whole size of the area is: BLK_HEAD + 22 + BLK_TAIL.

BLK_HEAD is usually 8 bytes, so working area is also aligned.
So, you have now 30 bytes + BLK_TAIL.

Closest 8 byte aligned size to this is 32 bytes (8*4), so
your BLK_TAIL is just 2 bytes, but for diagnostics you must fill it
with some value, like 0CDh and when block is getting freed -- you
check if the byte following the 22 bytes is still 0CDh and if it is not - block has been corrupted.

Isn't it fun?!..

AsmGuru62: That is basically the operation of HeapAlloc and LocalAlloc. You do realise that you are reinventing the wheel there, right?

Well, I need OS independent heap manager for FreshLib and probably will make one someday.
Isn't it better to keep some memory map for allocated/free blocks at some different place. For example, bit array with 1bit per 16bytes of memory.
This way, it is less probable, that the user can destroy the heap by writing outside the allocated block. You can separate the heap and the memory map by guard page.

Yes. The custom heap, however, provides more flexibility in some cases.
Or it can be optimized to a higher degree, since the owner of code is you and not Microsoft.