OSDev.org

• create_heap
• destroy_heap
• allocate
• release

• it can be placed at the HEAD of the free list, TAIL, inserted before the
  first free fragment having an ADDRESS exceeding that of the newly released
  fragment or before the first free fragment having a SIZE greater than the
  size of the fragment being released
• once inserted into the free list, it can be left AS_ALLOCATED as a free-standing
  fragment (retaining the size it had "in the wild"); or, if can be merged with
  "adjacent" fragments to COALLESCE and (possibly) reduce the number of
  fragments in the free list as well as enlarging those.

• the degree of heap sharing between potentially competing threads (i.e.,
  allow the request to proceed UNFETTERED as if there are no other competitors
  vying for these resources vs. ensuring ATOMIC operation in the presence of
  potential competitors)
• the extent of blocking tolerated by the request (i.e., return IMMEDIATEly
  if FAIL, block in the hope of completing the desired service but no longer
  than some specified TIMEOUT interval, WAIT indefinitely)

• fragment selection strategy: FIRST_FIT, LAST_FIT, BEST_FIT, WORST_FIT,
  EXACT_FIT, NEVER_FIT (the latter being a way to stress test applications)
• allocation trimming: TRIM, UNTRIMMED (i.e., if the fragment is larger than
  requested, should it be trimmed to maximize the amount of memory remaining
  in the free list?)
• free remainder: TAKE_HEAD, TAKE_TAIL (which part of the TRIMmed fragment
  should be returned to the caller vs. retained in the free list)
• size homogeneity: AS_REQUESTED, POWERS_OF_TWO, LISTED_VALUES,
  MULTIPLES (how should the specified SIZE be interpreted in locating a suitable
  free fragment)

• Generic code is rarely ideal for any specific purpose.

Brendan wrote: As a general rule of thumb:

• Generic code is rarely ideal for any specific purpose.

What you're doing is trying to create an over-complicated "swiss army knife". It will be useless for all the cases that can't be foreseen, and for all of the cases that were foreseen it will be a bloated mess due to support for cases that aren't needed by the application.

A better idea would be to provide functions to create and destroy memory pools, and then let the application provide its own heap manager/s that are custom designed specifically for the application (but also provide a simple "no frills" default heap manager for cases where the application simply doesn't care and is happy with any old "malloc() like" thing).

Don wrote:

What you're doing is trying to create an over-complicated "swiss army knife". It will be useless for all the cases that can't be foreseen, and for all of the cases that were foreseen it will be a bloated mess due to support for cases that aren't needed by the application.

Have you considered what is involved to handle each of the "options" I described?

Don wrote:Those that are more complicated (blocking in the allocator, opting for a lock on the heap itself -- or not) are required even if the simpler options are omitted/hardwired. They can't be efficiently implemented outside the memory manager.

Don wrote:Consider how you would allow a thread to wait for a particular allocation request to be handled -- in the absence of sufficient resources in the free list -- spin on the failing malloc()? And, hope no other thread sneaks in to grab any memory that becomes available while the other thread is busy spinning?

• implement a memory manager that has a list of waiters (including how much memory they're waiting for and their thread ID)
• when freeing memory; examine the list of waiters and if one or more of the waiters can be satisfied allocate the memory for them, and send a "here's the memory you were waiting for" message to the waiter
• Have waiters blocked waiting to receive a message (including "wait for message with timeout" and a way to remove a thread from the list of waiters, if and only if the specific application actually does need the extra complexity this involves)

Don wrote:I can, instead, wrap the "swiss army knife" implementation with "simple interfaces" for those cases that always need a specific set of options. A particular combination of options that are never used can simply not have a suitable wrapper provided.

allocBlock:
    mov eax,[nextBlock]
.retry:
    test eax,eax
    je .done
    mov edx,[eax]                          ;edx = next
    lock cmpxchg [nextBlock],edx
    jne .retry

    lock add [allocatedBlocksMinus5000],1  ;Should we send old entries to disk?
    jne .done                              ; no, "freeBlocks - 5000 != 0"
    lock bts [allocatedBlocksMinus5000],31  ;Set the "sending to disk in progress" flag (in highest bit)
    jc .done                            ;Don't notify if the "sending to disk in progress" was already set
    call startDiskPurge                    ;Notify the thread responsible for sending the log to disk
.done:
    ret

Don wrote:

A better idea would be to provide functions to create and destroy memory pools, and then let the application provide its own heap manager/s that are custom designed specifically for the application (but also provide a simple "no frills" default heap manager for cases where the application simply doesn't care and is happy with any old "malloc() like" thing).

The entire RTOS is "designed specifically for the application". I don't include "things that won't be needed" (unused features and capabilities) as those things cost resources. Those resources add to the selling price of the product. And, as I'm not hosting other applications (I design appliances, not workstation environments), there's no point in including support for things that might be used (but aren't).

it can be placed at the HEAD of the free list, TAIL, inserted before the
first free fragment having an ADDRESS exceeding that of the newly released
fragment or before the first free fragment having a SIZE greater than the
size of the fragment being released

Have you considered what is involved to handle each of the "options" I described?

Yes. For example, the "FIRST_FIT, LAST_FIT, BEST_FIT, WORST_FIT, EXACT_FIT, NEVER_FIT" menagerie implies that (internally) the memory manager is going to have to use an extremely stupid and slow "list of entries" approach to handle all the unnecessary options; and this will involve searching the list and can't/won't be "O(1)" for any/many of the important cases, and will therefore suck (and will probably suck so badly that it's completely unusable for "real-time" where you're meant to guarantee a worst case max. time for all operations and can't accept "searching an unknowable number of entries").

(pointer, size) := allocate(HEAP, BUFFER_SIZE, EXACT_FIT, FIRST_FIT, TRIM, TAKE_ANY, AS_REQUESTED);

result := release(HEAP, pointer, AT_HEAD, AS_ALLOCATED)

result := release(HEAP, pointer, AT_TAIL, AS_ALLOCATED)

Don wrote:Those that are more complicated (blocking in the allocator, opting for a lock on the heap itself -- or not) are required even if the simpler options are omitted/hardwired. They can't be efficiently implemented outside the memory manager.

The more "complicated" options are not required at all for most applications. If they can't be implemented efficiently inside an "application provided memory manager" (e.g. because applications can't use locks/mutexes/semaphores, or because your OS doesn't provide an efficient communication mechanism) then the OS will suck for a large number of things (that don't necessarily have anything to do with memory management).

I'm working in an embedded/appliance market on custom hardware. So, no constraints as to API's, porting legacy code, etc. The environment is real-time, multithreaded and object-based. The pieces of memory being managed are large-ish; the amount of memory available is significant.

Don wrote:Consider how you would allow a thread to wait for a particular allocation request to be handled -- in the absence of sufficient resources in the free list -- spin on the failing malloc()? And, hope no other thread sneaks in to grab any memory that becomes available while the other thread is busy spinning?

If, for some completely unimaginable reason I actually wanted to wait for memory (on an embedded system where my application is likely the only application, on hardware that was supposed to have a "significant" amount of memory available, on an OS that is supposed to be real-time and therefore supposed to guarantee maximum worst case times), I would:

• implement a memory manager that has a list of waiters (including how much memory they're waiting for and their thread ID)
• when freeing memory; examine the list of waiters and if one or more of the waiters can be satisfied allocate the memory for them, and send a "here's the memory you were waiting for" message to the waiter
• Have waiters blocked waiting to receive a message (including "wait for message with timeout" and a way to remove a thread from the list of waiters, if and only if the specific application actually does need the extra complexity this involves)

• I still have the resources (time, memory, I/O's, available power) to satisfy the GUARANTEED services that The System must provide to its users
• Joe User can't munge anything that he's not allowed to munge
• I can harvest Joe User's resources if other, "more pressing" demands materialize.

Don wrote:I can, instead, wrap the "swiss army knife" implementation with "simple interfaces" for those cases that always need a specific set of options. A particular combination of options that are never used can simply not have a suitable wrapper provided.

For a silly/simple example; lets say that (as part of my application) I want to log all packets sent and received over TCP/IP. I have a structure containing the details I want (dest IP address, etc) which includes a "next" field (because I'm planning to use a singly linked list of these structures) and this structure is exactly 123 bytes. For cache/TLB/data locality (performance) I want to ensure that the memory used for these structures is within the same range, so I allocate a memory pool specifically for these structures. I know (from CPU manufacturer info) that it's more efficient to align the structures on an 64-byte boundary (as this happens to be cache line size) so I'm looking at managing blocks of 128 bytes. When there are more than 5000 of these entries I want to append the oldest 2500 entries to a file on disk and free the memory the blocks used. I allocate a pool that's only large enough to allow 10000 entries to be allocated, and if that pool runs out of memory then I know that something must have gone wrong with disk IO so I terminate the application.

To get "O(1)" for everything that matters for this application (without any stupid "if(FIRST_FIT) { ....} else if(LAST_FIT) { ....}" branching/bloat); I create a pool (that is exactly "10000 * 128" bytes because that's all I need) and turn it into a singly linked list of free blocks (using the structure's "next" field that I already have). My application's "lockless" allocator (assuming 32-bit 80x86) looks like this:

count := 0
while (count < 10000) {
   (pointer, size) := allocate(HEAP, 128, EXACT_FIT, FIRST_FIT, TRIM, TAKE_TAIL, AS_REQUESTED);
   if (pointer != nil)
      result := release(HEAP, pointer, BY_LOCATION, AS_ALLOCATED)
}

I'd only free 2500 blocks at a time (and this is only ever done by the thread responsible for appending the data to the file on disk). This code would unlink the oldest 2500 entries, do the disk IO stuff, then merge the list of 2500 "now free" blocks with the allocator's list of free blocks in a single lockless "lock cmpxchg [nextBlock], ..." loop, then do a "lock sub allocatedBlocksMinus5000],2500 | (1 << 31)" to atomically adjust the number of allocated blocks and clear the "sending to disk in progress" flag at the same time.

Now see if you can tell me exactly how your "swiss army knife" would be used to implement this "application specific lockless allocator" better than the application's own custom designed allocator that I've described. Note that this is only one example (with relatively simple requirements), and an application may have/want many different allocators each specifically designed to be "as ideal as possible" for extremely different requirements/usage.

"OS designed specifically for the application" is an oxymoron. Either it's designed for one specific application and therefore it's part of one specific application and not an OS at all; or it's not designed specifically for one specific application.

gerryg400 wrote:I see two issues, although you may decide that they are unimportant for your project.

Firstly,

it can be placed at the HEAD of the free list, TAIL, inserted before the
first free fragment having an ADDRESS exceeding that of the newly released
fragment or before the first free fragment having a SIZE greater than the
size of the fragment being released

This seems to imply that you have already chosen a linked list to track free memory. In some small embedded systems this is okay but it doesn't scale for memory size and it doesn't scale for multicore. Furthermore you will lose the freedom to improve your internal algorithm because your interface describes your internals. You cannot change the internals without changing the interface.

Secondly, it looks like it would be fairly easy for a thread to use the options you provide to deliberately fragment memory. Not sure whether that's an issue for you or not.

I elected to express the operation in terms of a "list" -- its easier for people to associate "order" and "ranking" (by some set of criteria) with a sequential entity. Also to imagine how you can look at such a structure "backwards" to get complementary results. (e.g., WORST_FIT on a list sorted BY_SIZE suggests you start looking from the "end" instead of the "beginning")

gerryg400 wrote:

I elected to express the operation in terms of a "list" -- its easier for people to associate "order" and "ranking" (by some set of criteria) with a sequential entity. Also to imagine how you can look at such a structure "backwards" to get complementary results. (e.g., WORST_FIT on a list sorted BY_SIZE suggests you start looking from the "end" instead of the "beginning")

But what if there is not a list. What if you devise an algorithm where every free item is stored in a such a way that the correct size is immediately available and there is no opportunity to fit. In this case FIRST == LAST. If the user asked for WORST_FIT would you waste time looking for that when your algorithm has automatically already given you the PERFECT_FIT ?

And if so, why ?

In this case where there are actually no lists, what do HEAD and TAIL mean ?

Also, I think that by allowing the user to specify that free areas not be coalesced you make it difficult for perfectly fine algorithms like the 'boundary tag' algorithm to work optimally.

Don wrote:

Brendan wrote:

Don wrote:Have you considered what is involved to handle each of the "options" I described?

Yes. For example, the "FIRST_FIT, LAST_FIT, BEST_FIT, WORST_FIT, EXACT_FIT, NEVER_FIT" menagerie implies that (internally) the memory manager is going to have to use an extremely stupid and slow "list of entries" approach to handle all the unnecessary options; and this will involve searching the list and can't/won't be "O(1)" for any/many of the important cases, and will therefore suck (and will probably suck so badly that it's completely unusable for "real-time" where you're meant to guarantee a worst case max. time for all operations and can't accept "searching an unknowable number of entries").

Actually, it is MORE efficient (in time and space) exactly because the (efficient) developer KNOWS how the heap will be used and will take measures to ensure it remains in a state conducive to his future requests.

Don wrote:Consider how a buffer pool works; essentially, all you have is a list (regardless of whether implemented as such or as a bitmap, etc.) that allows you to locate AN available buffer -- in almost constant time (depends on how you represent "free").

How is that any different from:

Code: Select all

(pointer, size) := allocate(HEAP, BUFFER_SIZE, EXACT_FIT, FIRST_FIT, TRIM, TAKE_ANY, AS_REQUESTED);

?

Don wrote:

Brendan wrote:

Don wrote:Those that are more complicated (blocking in the allocator, opting for a lock on the heap itself -- or not) are required even if the simpler options are omitted/hardwired. They can't be efficiently implemented outside the memory manager.

The more "complicated" options are not required at all for most applications. If they can't be implemented efficiently inside an "application provided memory manager" (e.g. because applications can't use locks/mutexes/semaphores, or because your OS doesn't provide an efficient communication mechanism) then the OS will suck for a large number of things (that don't necessarily have anything to do with memory management).

What do you see the role of an operating system to be? Let's have the application developer write his own memory management routines, his own scheduler, his own file system, etc.?

Don wrote:In MY applications, the complicated options ARE required. Perhaps you missed:

I'm working in an embedded/appliance market on custom hardware. So, no constraints as to API's, porting legacy code, etc. The environment is real-time, multithreaded and object-based. The pieces of memory being managed are large-ish; the amount of memory available is significant.

Would you advocate each application sorting out how to handle its own deadline violations? Perhaps dedicate a hardware timer to each thread so IT could program the timer to notify it when its deadline has passed? Or, would you embody that as an OS service?

Would you advocate each thread and task/process communicate with its peers to come up with a mutually agreeable scheduling decision, NOW? Or, would you embody that as an OS service?

Don wrote:Would you insist that all memory consumers use a memory manager that imposes the overhead of a mutex on every access -- even if the memory manager is just being used by a single thread -- AT THIS TIME? Or, let each thread craft its own memory services??

Don wrote:

Brendan wrote:

Don wrote:Consider how you would allow a thread to wait for a particular allocation request to be handled -- in the absence of sufficient resources in the free list -- spin on the failing malloc()? And, hope no other thread sneaks in to grab any memory that becomes available while the other thread is busy spinning?

If, for some completely unimaginable reason I actually wanted to wait for memory (on an embedded system where my application is likely the only application, on hardware that was supposed to have a "significant" amount of memory available, on an OS that is supposed to be real-time and therefore supposed to guarantee maximum worst case times), I would:

• implement a memory manager that has a list of waiters (including how much memory they're waiting for and their thread ID)
• when freeing memory; examine the list of waiters and if one or more of the waiters can be satisfied allocate the memory for them, and send a "here's the memory you were waiting for" message to the waiter
• Have waiters blocked waiting to receive a message (including "wait for message with timeout" and a way to remove a thread from the list of waiters, if and only if the specific application actually does need the extra complexity this involves)

Your comments suggest you are thinking too small. I'm not designing a microwave oven. Or, a process control system that monitors a few dozen sensors and controls as many actuators. Possibly on a multimillion dollar piece of equipment.

Think scores of processors distributed over large areas (three-dimensional football fields). Tackling things like VoIP/video/audio delivery, location awareness, speech synthesis/recognition, security/access control, physical plant, etc. Think hundreds of applications and as many concurrent users.

• I am writing an OS that will be used for an unknown but very wide variety of very different applications; therefore it's inconceivable for me to cater to the specific requirements of every possible application; therefore I am unable to implement a memory manager that is "ideal" for all of the radically different usages. My "swiss army knife" memory manager must suck by definition; I should give applications the ability to provide their own custom designed alternative that doesn't suck for their specific usage; and if I do provide applications with the ability to use their own alternatives I don't have any reason to (attempt to and then fail to) cover all usages in a single memory manager in the first place."

Don wrote:And, unlike a desktop where the user can reboot, kill a job, hit reset, etc., I have to run, reliably, 24/7/365. If Joe User in cubicle #743 wants to "play pong", I have to ensure that:

• I still have the resources (time, memory, I/O's, available power) to satisfy the GUARANTEED services that The System must provide to its users
• Joe User can't munge anything that he's not allowed to munge
• I can harvest Joe User's resources if other, "more pressing" demands materialize.

Don wrote:

Brendan wrote:For a silly/simple example; lets say that (as part of my application) I want to log all packets sent and received over TCP/IP. I have a structure containing the details I want (dest IP address, etc) which includes a "next" field (because I'm planning to use a singly linked list of these structures) and this structure is exactly 123 bytes. For cache/TLB/data locality (performance) I want to ensure that the memory used for these structures is within the same range, so I allocate a memory pool specifically for these structures. I know (from CPU manufacturer info) that it's more efficient to align the structures on an 64-byte boundary (as this happens to be cache line size) so I'm looking at managing blocks of 128 bytes. When there are more than 5000 of these entries I want to append the oldest 2500 entries to a file on disk and free the memory the blocks used. I allocate a pool that's only large enough to allow 10000 entries to be allocated, and if that pool runs out of memory then I know that something must have gone wrong with disk IO so I terminate the application.

To get "O(1)" for everything that matters for this application (without any stupid "if(FIRST_FIT) { ....} else if(LAST_FIT) { ....}" branching/bloat); I create a pool (that is exactly "10000 * 128" bytes because that's all I need) and turn it into a singly linked list of free blocks (using the structure's "next" field that I already have). My application's "lockless" allocator (assuming 32-bit 80x86) looks like this:

Code: Select all

count := 0
while (count < 10000) {
   (pointer, size) := allocate(HEAP, 128, EXACT_FIT, FIRST_FIT, TRIM, TAKE_TAIL, AS_REQUESTED);
   if (pointer != nil)
      result := release(HEAP, pointer, BY_LOCATION, AS_ALLOCATED)
}

creates your 10000 128 byte buffers and ensures they are "ordered" BY_LOCATION.

Don wrote:The NEXT allocate request will yield the buffer having the lowest memory address -- and will provide it in constant time. The allocation after that will allocate the buffer having the next higher address -- in the exact same, constant time.

Don wrote:

Brendan wrote:I'd only free 2500 blocks at a time (and this is only ever done by the thread responsible for appending the data to the file on disk). This code would unlink the oldest 2500 entries, do the disk IO stuff, then merge the list of 2500 "now free" blocks with the allocator's list of free blocks in a single lockless "lock cmpxchg [nextBlock], ..." loop, then do a "lock sub allocatedBlocksMinus5000],2500 | (1 << 31)" to atomically adjust the number of allocated blocks and clear the "sending to disk in progress" flag at the same time.

Now see if you can tell me exactly how your "swiss army knife" would be used to implement this "application specific lockless allocator" better than the application's own custom designed allocator that I've described. Note that this is only one example (with relatively simple requirements), and an application may have/want many different allocators each specifically designed to be "as ideal as possible" for extremely different requirements/usage.

I counter (REAL example):

Don wrote:...you have live video coming off a camera on a node, "somewhere". You have to examine the video, in real time (i.e., it's an endless stream, even if you opt to buffer it somewhere, you still have to be able to process it at the same effective rate that it is being generated). You have to monitor for signs of motion in a certain portion of the image and signal an event when that is detected or persists for some period of time.

If you sense motion, you have to determine if a person is present (i.e., not just trees blowing in the breeze) and, if so, recognize his/her face. Based on who you do/don't recognize, you may have to unlock a door, connect a bidirectional audio stream between the guest and the receptionist, notify the boss that his wife has arrived, etc.

At the same time, you have to record all of this to persistent store.

And, present it for live review by an "attendant" located "in the guard shack".

Of course, Joe User shouldn't be able to eavesdrop on any of this stuff happening -- even if the resources to accomplish these tasks happen to be coming from "his" node!

And, all these "applications" are running on different device nodes scattered around the building. How many memory managers are you going to write to handle this "simple" set of applications? How much time are you going to devote to quantifying, documenting and validating each of their operations?

Don wrote:MIPS are dirt cheap. So is memory. Developer time is where the money gets wasted -- and user disappointment. "Gee, should I run each node at 300MHz? Or 600? 64MB of DRAM? or 256MB? One core or two? 100BaseTX or GBe?"

If I spend a few instruction fetches in a critical region... feh.

Don wrote:

Brendan wrote:"OS designed specifically for the application" is an oxymoron. Either it's designed for one specific application and therefore it's part of one specific application and not an OS at all; or it's not designed specifically for one specific application.

Seems like an arrogant assumption. Do you think embedded devices are just "spaghetti code" simply because YOU can't load an application of your own choosing onto it? Is a math library no longer a math library because a single application is using it? Amusing when you consider there are probably two orders of magnitude MORE embedded systems in the world than all the desktop machines combined!

Is Android only an OS *if* a user opts to load some non-default application onto it? I.e., if he uses the stock phone, as is, how does that differ from using an OS in a "single" application?

Don wrote:

gerryg400 wrote:

I elected to express the operation in terms of a "list" -- its easier for people to associate "order" and "ranking" (by some set of criteria) with a sequential entity. Also to imagine how you can look at such a structure "backwards" to get complementary results. (e.g., WORST_FIT on a list sorted BY_SIZE suggests you start looking from the "end" instead of the "beginning")

But what if there is not a list. What if you devise an algorithm where every free item is stored in a such a way that the correct size is immediately available and there is no opportunity to fit. In this case FIRST == LAST. If the user asked for WORST_FIT would you waste time looking for that when your algorithm has automatically already given you the PERFECT_FIT ?

Yes.

Don wrote:

And if so, why ?

How would you issue a request for the smallest fragment in the heap? Or, the largest? Do you want to expose the sizes of all fragments to the caller directly and let him choose?

YOU know what your code is going to do with the memory. YOU know what you've already extracted from the heap. Presumably, YOU know how you want to use the current/remaining contents of that block of memory. You're not dealing with an subsystem that has to be able to fit with "generic" applications but, rather, with very specific ones.

Why not create all buffers to be exactly a page size -- on the premise that you can move them more effectively and consistently via RPC than having to marshall itsy-bitsy individual arguments? It's far easier for me to move pages between nodes than it is to move a hundred bytes up and down the protocol stack; why not force all API's to exploit big blocks of data (like moving chunks of audio and video around)?

Don wrote:

In this case where there are actually no lists, what do HEAD and TAIL mean ?

Depends on how the developer has elected to place released fragments into the "list". If he's asked for them to be "inserted" by location, then "TAIL" means "the fragment occurring at the highest memory address". If he's asked for them to be inserted by size, then "HEAD" means "the smallest fragment". Can you come up with a better lexicon to convey these concepts?