common dynamic memory allocator API

[rdos]

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?

Huh? The physical memory manager handles allocating and freeing physical pages. It has nothing to do with allocating linear address space. In my design, physical memory for a linear adress is almost always allocated by the pagefault handler. The only exception is some device-drivers using DMA.

[gravaera]

@rdos: Please stop going on and on about your gangsta "assembly only" OS: it's off topic. If you think that this proposal doesn't suit your kernel, then don't use it.

[JamesM]

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.

No, you're quite right. I certainly haven't got to the stage of jumping to user mode.

Douche.

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.

FYI, memory allocated by user applications running on a non-kernel ring will not use the kernel heap allocator, will they?. Honestly, if you are going to ruin every single intellectual discussion on this forum with the limitations and failure to properly encapsulate functionality in your own OS, please engage brain before replying.

"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.

On-demand page allocation makes a lot of sense, but not in this area. If I call "malloc(32)", the likelihood is that I'm going to use those 32 bytes very shortly, if not immediately. For no other reason, maybe, than to memset(ptr, 0, 32). If I've specifically requested some heap memory, why try and second-guess me and assume I'm not going to access it soon? You're wasting time with that page fault.

Now, if we were talking about some other memory subsystem, like a file being memory-mapped or a large memory-mapped area; yes, I agree with you.

But we're not, so I don't.

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".

I use the word "heap" because it is called a heap.

I could call it a "camel", instead. But I wouldn't, because it's a heap.

[Solar]

In an attempt to get this back on track...

Unless I am mistaken, what Nick suggested is an API "standard" for memory-related system calls to be called from user space.

The idea would be that your user-space implementation of malloc(), free(), realloc() etc. etc. doesn't have to bother with whether your kernel uses something like sbrk() or mmap() or whatever to actually provide that memory. (Perhaps you could use this abstraction layer even for kernel-space work.) Right?

As such, I certainly see benefits there. If anything, it would make the implementation of that particular corner of my PDCLib real easy. I don't really look forward to adapting my C library to a multitude of memory-handling system calls that are out there.

Please tell me if I'm on the right track here or whether I have misunderstood the whole thing, before I try to contribute "in the wrong direction".

@ rdos:

You have code, data, stack, and heap. That's standard nomenclature in software engineering. You can call it whatever you like, but you'll have to deal with the fact that those names are used by virtually everybody else, and will have problems with whatever custom nomenclature you might have come up with.

[JamesM]

In an attempt to get this back on track...

Unless I am mistaken, what Nick suggested is an API "standard" for memory-related system calls to be called from user space.

The idea would be that your user-space implementation of malloc(), free(), realloc() etc. etc. doesn't have to bother with whether your kernel uses something like sbrk() or mmap() or whatever to actually provide that memory. (Perhaps you could use this abstraction layer even for kernel-space work.) Right?

As such, I certainly see benefits there. If anything, it would make the implementation of that particular corner of my PDCLib real easy. I don't really look forward to adapting my C library to a multitude of memory-handling system calls that are out there.

Please tell me if I'm on the right track here or whether I have misunderstood the whole thing, before I try to contribute "in the wrong direction".

@ rdos:

You have code, data, stack, and heap. That's standard nomenclature in software engineering. You can call it whatever you like, but you'll have to deal with the fact that those names are used by virtually everybody else, and will have problems with whatever custom nomenclature you might have come up with.

I took Nick's suggestion (even though he hinted at use for userspace also) as mainly for the kernel memory allocator. The sheer number of heap allocations and deallocations means that a syscall for each would be extremely wasteful, which is why the mmap/sbrk interface between userspace and kernelspace is used in the first place.

[Solar]

The sheer number of heap allocations and deallocations means that a syscall for each would be extremely wasteful, which is why the mmap/sbrk interface between userspace and kernelspace is used in the first place.

Of course a user-space malloc() would usually allocate a larger chunk of memory at once, and parcel it out to the application, instead of making a system call for every allocation.

But mmap / sbrk are not exactly "standard" (unless you're only looking at the POSIX world), and not very elegant either. Especially sbrk() is severely leaking abstraction, and mmap() isn't what I would call a "slim" interface either.

Consider: If you're using sbrk(), you cannot return memory to the system unless the topmost "chunk" of memory has been completely deallocated by the application - even if one or more "chunks" below that have been deallocated already (because sbrk() is strictly linear).

And you can't easily switch between sbrk() and mmap() as the memory-providing syscalls either. Nick's suggested API would make things much easier on the system malloc().

I am already considering Nick's API suggestions as the abstraction level for the PDCLib malloc(). That's why I joined this thread.

[JamesM]

The sheer number of heap allocations and deallocations means that a syscall for each would be extremely wasteful, which is why the mmap/sbrk interface between userspace and kernelspace is used in the first place.

Of course a user-space malloc() would usually allocate a larger chunk of memory at once, and parcel it out to the application, instead of making a system call for every allocation.

But mmap / sbrk are not exactly "standard" (unless you're only looking at the POSIX world), and not very elegant either. Especially sbrk() is severely leaking abstraction, and mmap() isn't what I would call a "slim" interface either.

Consider: If you're using sbrk(), you cannot return memory to the system unless the topmost "chunk" of memory has been completely deallocated by the application - even if the "chunks" below that have been deallocated already. And you can't easily switch between sbrk() and mmap() as the memory-providing syscalls either. Nick's suggested API would make things much easier on the system malloc()...

Absolutely, but unless you extend the scope of this drastically you're not going to be able to define a replacement. My impression of Nick's suggestion was just the generic heap allocation/tracking algorithm with the thinnest possible wrapper to the outside world.

[Solar]

Absolutely, but unless you extend the scope of this drastically you're not going to be able to define a replacement.

Anyone wanting to use my C library and not being able to serve my abstraction layer is welcome to maintain his own set of patches to make PDCLib work with his OS API.

The "abstraction layer" I am using for my makeshift malloc() is ridiculous (thinly disguised sbrk()), and cannot return memory to the system at all. And I am not going for sbrk() / mmap() as the "abstraction layer" either. That's why I am interested in Nick's concept (if I understood it correctly, as I said).

Nick?

[JamesM]

Absolutely, but unless you extend the scope of this drastically you're not going to be able to define a replacement.

Anyone wanting to use my C library and not being able to serve my abstraction layer is welcome to maintain his own set of patches to make PDCLib work with his OS API.

The "abstraction layer" I am using for my makeshift malloc() is ridiculous (thinly disguised sbrk()), and cannot return memory to the system at all. And I am not going for sbrk() / mmap() as the "abstraction layer" either. That's why I am interested in Nick's concept (if I understood it correctly, as I said).

Nick?

I think if you understood it correctly, then I understood it incorrectly, and vice versa!

Nick?

[rdos]

Consider: If you're using sbrk(), you cannot return memory to the system unless the topmost "chunk" of memory has been completely deallocated by the application - even if one or more "chunks" below that have been deallocated already (because sbrk() is strictly linear).

I'm not sure about why this would matter. If we consider a paged OS where each user program runs in its own address space, it won't matter if you can return memory or not. You are basically allocating linear memory in the application's private address space, so there is no need for returning anything. Actually, I personally see no use in sbrk() either, as the entire private linear address space is already committed to the application.

[gerryg400]

Consider: If you're using sbrk(), you cannot return memory to the system unless the topmost "chunk" of memory has been completely deallocated by the application - even if one or more "chunks" below that have been deallocated already (because sbrk() is strictly linear).

I'm not sure about why this would matter. If we consider a paged OS where each user program runs in its own address space, it won't matter if you can return memory or not. You are basically allocating linear memory in the application's private address space, so there is no need for returning anything. Actually, I personally see no use in sbrk() either, as the entire private linear address space is already committed to the application.

Returning memory (by lowering the brk pointer or using munmap) tells the memory manager explicitly that the associated physical memory is no longer needed by the application.

[NickJohnson]

@JamesM/Solar: You're sort of both right. One point is to have an abstraction layer (not standardized system calls, just a wrapper) over native OS memory management functions, so that allocators could be written portably. The other is to have a standard interface for written allocators, so any allocator written for the API can be used with any library/kernel/whatever implementing the API. So it's really two APIs: one for building allocators, and one for allocators to implement.

The set of functions I originally posted was for the allocators to implement. Those three functions seem to encompass all needed functionality. The things I'm not sure of are the best way to make allocators provide those frontend functions to the system (just normal functions? function pointers in structures?), and the best way to make a wrapper over various OS memory management functions.

The idea is to have these allocators available for not only kernels but also C libraries (I happen to be writing my own, and PDCLib seems to have a pretty stubbed-out malloc.) And possibly even applications that need special allocators for speed (things like Firefox seem to have internal APIs like this to handle different allocator options.) Of course, the last one falls outside the realm of osdev...

So, to try and get this discussion back on track:

What low level memory management functions are common enough to need to accommodate with this wrapper? (mmap/munmap (for kernels and some userspaces) and brk (simpler *nix systems) at least, but flat, unpaged systems should be considered too.) What should constitute the wrapper?

[rdos]

I'm not sure about why this would matter. If we consider a paged OS where each user program runs in its own address space, it won't matter if you can return memory or not. You are basically allocating linear memory in the application's private address space, so there is no need for returning anything. Actually, I personally see no use in sbrk() either, as the entire private linear address space is already committed to the application.

Returning memory (by lowering the brk pointer or using munmap) tells the memory manager explicitly that the associated physical memory is no longer needed by the application.

Yes, but as have already been discussed, few, if any, allocators that grabs a piece of memory will ever be able to return some of it back to the OS, so linear address space that have been comitted for physical storage never free the physical storage. Instead, typical loaders free the whole address-space once the application terminates. The exception is segmented designs, where the selector base can be changed, and thus the heap can be compacted and partly released.

To solve this problem (for larger allocations), it is much better to allocate directly from the page-tables (page-aligned), and then the physical pages can be freed once the allocation is freed. This is possible because there is no other allocation affected when the pages are freed. It can be done for "memory subdividers" as well, but the algorithm is more complex. The allocator needs to find entire pages that are free, and then free their physical storage.

[Solar]

...few, if any, allocators that grabs a piece of memory will ever be able to return some of it back to the OS...

To cut this short, I would consider any such allocator to be broken by design and unfit for use in any "serious" OS.

[gerryg400]

Rdos, what on earth are you talking about ?

few, if any, allocators that grabs a piece of memory will ever be able to return some of it back to the OS, so linear address space that have been comitted for physical storage never free the physical storage.

That's not true. Many allocators including the malloc() that I use (from newlib) can munmap memory during free() if the O/S supports it. Most do.

BTW, my post was in response to a statement you made saying

I'm not sure about why this would matter. If we consider a paged OS where each user program runs in its own address space, it won't matter if you can return memory or not. You are basically allocating linear memory in the application's private address space, so there is no need for returning anything.

So you start by saying that it doesn't matter whether or not memory is returned memory to the system and conclude with 'a much better way' to return memory to the system.