common dynamic memory allocator API

[NickJohnson]

It seems that dynamic memory allocation is one of the few things in OS development that is both critical and almost completely independent of processor and kernel architecture, at least in theory. I think we should develop an API for writing platform-independent dynamic memory allocators, one that would be easy to implement in the kernel or C library but give access to a well-designed (and, more importantly, thoroughly tested) set of allocators.

Through my own experiences, I believe that there are exactly three functions that a dynamic memory allocator should have to support:

First, a function to allocate memory with a specific alignment (if the alignment is a special value, like 0, it would be ignored; if it is impossible for the allocator to allocate with an alignment, it could reject the request). This function would allow creation of malloc(), calloc(), valloc(), and posix_memalign() etc. E.g.

Code: Select all

void *heap_alloc(size_t size, size_t align);

Second, a function to give the allocated size of a pointer (which would be greater than or equal to the requested size); this function could also return a special value (0) when the pointer is not from the heap, allowing programs to decide whether to free pointers in certain situations, for example. This function would also be necessary for realloc(). E.g.

Code: Select all

size_t heap_size(void *ptr);

Third, a function to free memory. This is just free(), obviously. E.g.

Code: Select all

void heap_free(void *ptr);

However, depending on whether the OS uses a brk() style of low level memory allocation or an mmap() style of low level memory allocation, the internals of a memory allocator are usually different. brk() can be trivially implemented using mmap(), so all allocators should be required to be able to use brk() style, but could then have options (via preprocessor flags) to take advantage of the mmap() style if it is available.

I think that headers and example functions detailing the API should be written in C, and the allocators themselves in C or assembly, so that C++, C, and assembly programmers can all have access to allocators with no modification. Licensing under a BSD-style or similarly liberal license would obviously be preferred, because the allocators are useless without integration into a project.

Does this idea sound reasonable? Would people be willing to write/port some allocators?

[rdos]

I have a lot more variation than that. First, I have a byte-aligned allocator (which uses memory-control blocks), and a page-aligned allocator which allocates memory with page-tables. These are for kernel-only accessible memory that is global to the whole system. Then I have per-process memory in both of these configurations (byte-aligned and page-aligned), that are local to a process. Lastly, I have a function to allocate memory that is per-process, but that has a fixed address in every process.

If this was not enough, there also exists variations that allocates selectors rather than linear addresses for all of the above.

For spotting errors in applications, I also have a special memory-allocator that allocates every request from new / malloc into a new page-frame, skips one page-frame and fills-out the unused portion with a signature. When the block is freed, the unused portion is verified against the signature for overwrites. The page-tables are also not reused, but rather every new allocation starts one page after the last, trapping accesses to freed memory. I think this is a must tool for C/C++ programmers.

[NickJohnson]

I don't see your problem: I never said that you couldn't have multiple allocators. I admit that allocating selectors would be tricky with this method, but you're really going to have to modify or rewrite any normal allocator (i.e. one that can be used with C/C++) to work with segmentation anyway, so it's outside the domain of the idea.

What I meant by those function prototypes was the general type of function that would need to be implemented (i.e. what arguments, what return values.) The best way to implement an allocator API would probably involve instantiating allocator implementations with structures containing function pointers. Nobody seems that interested, so I haven't come up with any precise implementation details.

[Creature]

I like the idea of having a library for memory allocation. I pretty much like anything that tries to 'standardize' implementations across our OS'. I'm a little low on time right now, so I can't help with implementation, but I'd be happy to try and discuss the subject in this topic. The memory allocator is something that is hard to get completely right and usually requires a lot of debugging, so getting one fully working implementation up seems like a nice idea.

I agree with implementing it in C and Assembly. Even though I prefer C++, doing it in C and/or Assembly allows not only C++-programmers to use the library. Heck, even people programming in other languages (such as Pascal) may be able to get the library linked in.

I also suggest there'd be some sort of "initialize" function (or somehow do this through brk()) that allows you to tell the memory allocator where it is located or the first block should start. This way you can take care of mapping that part of virtual memory in. The rest of 'heap expansion' would then go through brk() or a similar function.

Finally, maybe it would be feasible to have multiple types of memory allocators inside the API, such as a standard allocator, a slab allocator, and so on for specific purposes. I only see one problem however: will different architectures be supported? For starters, x86-32 seems feasible, but x86-64 OS' may want to take advantage of larger address spaces or 8-byte integers. Similarly, other architectures like ARM may require other implementations. You could also of course limit yourself to the x86 or a couple of architectures.

[rdos]

I think you missed some of my point. A page-aligned allocator needs to be aware of paging, and page-tables. It cannot stand alone. A byte-aligned allocator might be more stand-alone, but it still requires some kind of integration into the paging system in order to operate properly (mostly because unallocated space should page-fault when referenced, and for allocating physical memory in page-tables).

I also don't think a C/C++ implementation of a memory allocator could possibly be used in an assembler-only OS, as it might require some C-library support.

BTW, there is another aspect as well. Memory for file-system buffers. It is usually a good idea to use free physical memory for file system buffers, but this also require file system buffers to be allocated in a special way, and to be reclaimed when physical memory is low.

And then there is the whole issue of managing and allocating physical memory in an OS that uses paging.

[NickJohnson]

It's much less a library than an API that can be implemented in a C library or kernel that has implementations written for it. Similar idea to CDI/UDI, but substitute driver with allocator.

I also suggest there'd be some sort of "initialize" function (or somehow do this through brk()) that allows you to tell the memory allocator where it is located or the first block should start. This way you can take care of mapping that part of virtual memory in. The rest of 'heap expansion' would then go through brk() or a similar function.

I recently had an idea about this, and the whole issue of low level memory management. You would give some sort of an initializer function the initial virtual memory region, then the allocator could request additional virtual memory from the OS. However, the actual state of these regions would be undefined: the allocator would call an "activate" function on a region to make sure there are frames with certain permissions in it, and a "deactivate" function to release that region from the need to have frames. The system could decide whether to have all regions preallocated (or not use paging) and ignore these calls, or to respond to these calls.

Finally, maybe it would be feasible to have multiple types of memory allocators inside the API, such as a standard allocator, a slab allocator, and so on for specific purposes. I only see one problem however: will different architectures be supported? For starters, x86-32 seems feasible, but x86-64 OS' may want to take advantage of larger address spaces or 8-byte integers. Similarly, other architectures like ARM may require other implementations. You could also of course limit yourself to the x86 or a couple of architectures.

I think it makes most sense to make allocators instantiated (as structure-objects), so you can have any number of duplicate or different allocators on a system. The kernel/library writer would be responsible for plugging specific instances into things like malloc(), free(), etc. Allocators can easily be written to be portable across architectures and 16/32/64 bit, by using appropriate types like uintptr_t. A C allocator is as portable as C itself. Similarly, for assembly-written allocators, it will be architecture specific.

I think we can assume a flat (probably paged) address space, and that will work. By probably paged, I mean the allocators could be designed for paged systems, but if the system is not paged, all it will suffer is a loss in memory efficiency. You could easily have allocators written specifically to assume a non-paged system, but even these would work on a paged system too.

I think you missed some of my point. A page-aligned allocator needs to be aware of paging, and page-tables. It cannot stand alone. A byte-aligned allocator might be more stand-alone, but it still requires some kind of integration into the paging system in order to operate properly (mostly because unallocated space should page-fault when referenced, and for allocating physical memory in page-tables).

I also don't think a C/C++ implementation of a memory allocator could possibly be used in an assembler-only OS, as it might require some C-library support.

A page aligned allocator does have to be aware of the page size, but nothing else. The paging system, even in the kernel, can be invoked in an OS-agnostic way just like in the C library.

It would work to have a small set of the C library string functions (memcpy, memset should be enough); this is as much of the C library as would be needed, and not much trouble to implement in assembly. The major issue for assembly programmers is that every interface function would require using the same calling convention as the C compiler's calling convention (usually cdecl). Without guaranteeing this, it would be impossible to have a real cross-platform API.

[rdos]

A page aligned allocator does have to be aware of the page size, but nothing else. The paging system, even in the kernel, can be invoked in an OS-agnostic way just like in the C library.

Not true. The page tables and page directories are not directly accessible, rather needs to be mapped into the virtual address space at some (OS dependent) positions where they can be manipulated by for instance a memory allocator, but also by things like demand-loading pages from an executable user program in PE or ELF format. Also, there needs to be some kind of agreement between the OS and the memory allocator as to what the free bits in the page-frames means, and how to mark pages as present (but not mapped to physical pages). Unless you want to commit every allocation to physical memory directly, which would be quite ineffecient. And in the latter case there will be a need to allocate a physical page, which would be OS-dependent.

[rdos]

If we look at flat user programs (and their requirements), they will need low-level (OS) functions for allocating pages, setting page-attributes and for marking pages as present/not present once they are allocated. There is also a need to bind pages to sections in the executable file, but this can be handled by a OS-level loader. Then the C-library will contain functions for subdividing pages into actual allocated space (from new, malloc).

So, the simple interface proposed here will not fulfill the basic needs for a user-level image, as it will at least need some functions for setting access rights.

Device-drivers in kernels will typically have some additional needs. They will need to be able to allocate pages in both user-space and kernel-space, and will need to subdivide them (if the kernel doesn't support this). They might also need to allocate kernel space both in the current process and globally. There might be a need for per-thread memory as well.

[JamesM]

If we look at flat user programs (and their requirements), they will need low-level (OS) functions for allocating pages, setting page-attributes and for marking pages as present/not present once they are allocated. There is also a need to bind pages to sections in the executable file, but this can be handled by a OS-level loader. Then the C-library will contain functions for subdividing pages into actual allocated space (from new, malloc).

So, the simple interface proposed here will not fulfill the basic needs for a user-level image, as it will at least need some functions for setting access rights.

Device-drivers in kernels will typically have some additional needs. They will need to be able to allocate pages in both user-space and kernel-space, and will need to subdivide them (if the kernel doesn't support this). They might also need to allocate kernel space both in the current process and globally. There might be a need for per-thread memory as well.

You seem to place a lot of stress on the comprehension of "pages" seemingly throughout your user and kernel model. Might I suggest that many hobby OS kernels out there have a tad more seperation of the concepts of physical, virtual and heap memory management than yourself?

Not that it's a bad thing, it's just you don't seem to have the same level of abstraction as others. Yes - DMA requires areas to be page aligned and mapped at a certain area - but that's neither the heap manager's remit nor problem.

[rdos]

You seem to place a lot of stress on the comprehension of "pages" seemingly throughout your user and kernel model. Might I suggest that many hobby OS kernels out there have a tad more seperation of the concepts of physical, virtual and heap memory management than yourself?

"Heap memory management" is a C/C++ concept, and as such does not fit with OSes that use assembly. The equivalent is the byte-aligned allocator I talked about above, which does the same thing that the C-library does for implementing the "heap".

But it is also true that no linear memory allocation algorithm in a paged system can live alone. Any sane implementation needs support for marking pages as present/not present, and setting access attributes (kernel/user and read/write). Without segmentation, these are the only means of access protection available. And physical memory needs to be allocated, either in the page-fault handler or when allocating memory. A byte-aligned allocator might not provide the fine-grained access protection features, but it still needs to cooperate with paging.

And for those that have studied the Win32-API knows exactly what I talk about regarding manipulation of page-tables that are included there, and which also are needed when loading both PE and ELF executables.

Finally, "memmap" is basically another method of manipulating page-tables.

[Owen]

You seem to place a lot of stress on the comprehension of "pages" seemingly throughout your user and kernel model. Might I suggest that many hobby OS kernels out there have a tad more seperation of the concepts of physical, virtual and heap memory management than yourself?

"Heap memory management" is a C/C++ concept, and as such does not fit with OSes that use assembly. The equivalent is the byte-aligned allocator I talked about above, which does the same thing that the C-library does for implementing the "heap".

But it is also true that no linear memory allocation algorithm in a paged system can live alone. Any sane implementation needs support for marking pages as present/not present, and setting access attributes (kernel/user and read/write). Without segmentation, these are the only means of access protection available. And physical memory needs to be allocated, either in the page-fault handler or when allocating memory. A byte-aligned allocator might not provide the fine-grained access protection features, but it still needs to cooperate with paging.

And for those that have studied the Win32-API knows exactly what I talk about regarding manipulation of page-tables that are included there, and which also are needed when loading both PE and ELF executables.

Finally, "memmap" is basically another method of manipulating page-tables.

Firstly, the C heap manager does not return "byte-aligned" memory (on any reasonably modern system), as doing so would be both terribly non-performant and non-conformant. Secondly, the concept of a "heap" is a rather generic concept; garbage collected languages also use the same time.

Now, as for marking pages not present or present, and access bits: That is a whole layer below any general purpose memory allocator. The allocator does not care; all it needs to know is (a) how to get writable pages and (b) how to dispose of them. Page permissions are a matter for the operating system, and I think most people will agree that a general purpose allocator has little need for controlling them (Not that no allocator does; but a general purpose one simply needs to allocate writable memory)

Yes, if you include an allocator which returns writable and executable memory (And I don't know why you would be silly enough to do so, but there you go) then it will need extra features; but that is different problem from the one that this thread is about.

[rdos]

Firstly, the C heap manager does not return "byte-aligned" memory (on any reasonably modern system), as doing so would be both terribly non-performant and non-conformant. Secondly, the concept of a "heap" is a rather generic concept; garbage collected languages also use the same time.

OK, make that word-aligned, dword-aligned, qword-aligned or whatever is most optimal for the particular CPU. It is still different from page-aligned, which could be implemented without any type of memory-control blocks.

Now, as for marking pages not present or present, and access bits: That is a whole layer below any general purpose memory allocator. The allocator does not care; all it needs to know is (a) how to get writable pages and (b) how to dispose of them. Page permissions are a matter for the operating system, and I think most people will agree that a general purpose allocator has little need for controlling them (Not that no allocator does; but a general purpose one simply needs to allocate writable memory)

I thought we talked about the needs of the operating system.

Are you saying this thread is about the needs of typical applications? In that case I see no need for a standard at all, as the typical runtime-library will take care of this for you.

[JamesM]

Firstly, the C heap manager does not return "byte-aligned" memory (on any reasonably modern system), as doing so would be both terribly non-performant and non-conformant. Secondly, the concept of a "heap" is a rather generic concept; garbage collected languages also use the same time.

OK, make that word-aligned, dword-aligned, qword-aligned or whatever is most optimal for the particular CPU. It is still different from page-aligned, which could be implemented without any type of memory-control blocks.

Now, as for marking pages not present or present, and access bits: That is a whole layer below any general purpose memory allocator. The allocator does not care; all it needs to know is (a) how to get writable pages and (b) how to dispose of them. Page permissions are a matter for the operating system, and I think most people will agree that a general purpose allocator has little need for controlling them (Not that no allocator does; but a general purpose one simply needs to allocate writable memory)

I thought we talked about the needs of the operating system.

Quite. In general the heap serving an OS kernel should not need to worry about permissions, as the memory it serves will always be accessed in supervisor mode. "Get a page" from the physical memory allocator, map it using the virtual memory manager, carve it up in some heap-algorithm-specific way, track it, return parts of it, dispose of it back to the physical memory manager at some point when it is free again.

No permissions setting needed. You'd need interfaces to the PMM and VMM, but nothing major.

Oh, and a "heap" is a dynamically-sized store of data with global scope. Even for assembly, you use the stack for local data (or promote directly to registers) -data with scope longer than the current routine invocation must be either placed statically in global memory or allocated on <some kind of> heap. Whether you call it that or not.

[JamesM]

It is still different from page-aligned, which could be implemented without any type of memory-control blocks.

This is what a physical memory manager is for. Dear me, you really have difficulty with the concept of encapsulation, don't you?

[rdos]

Quite. In general the heap serving an OS kernel should not need to worry about permissions, as the memory it serves will always be accessed in supervisor mode.

Really? I suppose you haven't yet come to the stage where you run applications on user-level ring. Or do you mean that user applications will run at kernel ring, and be able to mess up OS data?

FYI, memory allocated by user applications running on non-kernel ring, will need OS support for allocating memory, and you just cannot hand it memory allocated for supervisor mode. Well, you can, but it would be a lousy system.

"Get a page" from the physical memory allocator, map it using the virtual memory manager, carve it up in some heap-algorithm-specific way, track it, return parts of it, dispose of it back to the physical memory manager at some point when it is free again.

That's not how I allocate kernel memory. I use the page-fault handler to allocate physical memory. No sense in commiting memory to physical storage that is not accessed. Besides, an allocation might need to allocate physical memory for both the page itself and a new page-directory. This complexity is better hidden in the page-fault handler than in the memory allocator. This is why there is a need to mark pages as "present-but-not commited-to-physical-memory". But, then, again, I suppose you could let kernel access any address and automatically commit physical memory to it when it wants it, but that is also a lousy solution.

Oh, and a "heap" is a dynamically-sized store of data with global scope. Even for assembly, you use the stack for local data (or promote directly to registers) -data with scope longer than the current routine invocation must be either placed statically in global memory or allocated on <some kind of> heap. Whether you call it that or not.

I see no reason to use the word "heap". You allocate a piece of memory, that's it. Depending on the size of the request, it either allocates a page-aligned block with the help of page-tables or with smaller alignment using memory control blocks. The device-driver using it couldn't care less how it is allocated. There is especially no need for any heap-handles like M$ uses in their Win32 system, and without a heap-handle there is no reason to use the word "heap" either.