Portable ADT Library Questions

[elderK]

Hey guys!

Im doing some research for the Portable ADT Library, particularly on how the various Operating Systems in development here allocate memory.

This is important to how I code the Library. My goal is simple.

- Make the Library as portable as possible, easily able to modify to execute within the majority of OSes in development on these boards.

- Modification done within Wrapper functions, that interface between the Library and the Operating System. By modifying only a few Wrapper / Gateway functions, the majority of the Library's code can be left (Saving novices headaches?).

This being said, I need to research HOW the majority of systems allocate memory, so that I can decide on the number of Gateway functions. (If special initialization is needed, etc).

For example, Zenobit's block allocator is called the ABM. The ABM is nothing like the usual MALLOC that we all become used to (atleast, In UNIX?). ABM is a Pool system. Pools are configured to deal out units of a set size. So, Portable ADT Library will need initialization functions for Zenobit, to create the Node Pool.

I was just wondering how many other people had odd / interesting allocation mechanisms.

~zeii.

[elderK]

If anyone would like me to clarify the various different approaches to Memory management, give me a yell.

~zeii.

[Bob the Avenger]

Mines not to complex/odd, I can allocate page by page physical and virtual memory using a stack and a list respectively. I also have a heap which i can allocate byte by byte from using a bitmap.

Peace

[serishema]

my operating system project allocates memory through the object manager.

so in kernel mode as a non SIP (software isolated process) thread you'd create a virtual page group object for the number of pages you want of the given page size, if you don't specify a page size the default for the SYSTEM process is used (the hardwares' page size). Virtual Page groups that are not a multiple of the hardwares' page size are discouraged because they reduce the performance of the JITer runtime.
The allocated virtual pages are really allocated on the runtime abstract stack and the returned virtual address is a pointer to this memory which the runtime ensures appears continuous. Each page is really an instance of a CTS class provided by the operating system which holds the data on the abstract stack. These pages are stored in a CTS System.Array

Physical address must never be used as they may become invalid without warning which could possibly crash the runtime.

For a SIP (software isolated process) virtual page group objects are not allowed and instead you eaither create an object instance on the managed heap (C/C++) or use the C# new operator.

the jitter runtime itself uses a simple free page stack approach.
it presents the usual .NET runtime type environment to the kernel.
the kernel in turn provides an environment that is more compatable with programs written in ASM,C or C++

the object manager simply keeps track of what process owns what object on the abstract stack (managed heap) and interfaces with the JITer runtime using privileged methods to enforce memory protection. This is maintained as a hashtable where the key is the Object.Hashcode() of the instance and the data is the process ID.

Outside of kernel mode the POSIX personality layer (which i haven't written yet) will provide the familar malloc() and the very different approach to memory management due to the operating system's managed code nature being written in C# will be completely hidden from your program as well as the fact that your programs' x86 instrctions are being recompiled into MSIL and then jitted.

Finally when programming for MyOS in unmanaged C/C++ all compiler optimizations must be disabled as they will confuse the runtime and make your program significantly slower. A major difference that can affect performance is the fact that when you write for MyOS you are not targeting the CPU, you are targeting a compiler because of the way the operating system works.

[frank]

I would say that you should leave any memory specific setup to the kernel. Give them a little warning somewhere that says that they will need an allocator that will return a pointer to a memory location of a certain length and that your library will do nothing to setup memory allocations. I also believe that any good kernel will at least have decent malloc implementation.

[elderK]

Well, yes. Of course.

Which is why im asking.

The library will define several macros, and prototype several 'gateway' functions.

These functions are up to the person using the Library, to modify. It is these functions which interface with that persons Kernel.

This library itself, doesnt do the memory management itself, it just provides an interface between itself and the Kernel it is being shoved into.

That being said, some Kernels use radically different approaches to Memory Management. Some use the generic Malloc approach, some dont.

Some assume Software will handle memory itself, some create Pools of certain structures.

Thus the optional Initialization routines that the library will also prototype. That way, The person can put whatever they need in that Initialization function so that the other Gateway functions (used for Allocation) will actually work.

Maybe later I will explain Zenobit's Memory management system in a little detail, then people can understand all the complication.

~zeii.

[elderK]

Alright, Allocation issues aside (Ive decided that frank was right, I was just complicating things, as I tend to do from time to time).

Are you guys all okay with 17b sized AVL Nodes? I figured Keyless-AVL nodes would be very difficult to use, since the AVL_NODE's memory address itself, would be the key.

BST Nodes are 12b (until further notice).
SLL are 4.
DLL are 8.

sll/dll nodes have no key. They are just links. Im deciding whether or not to give them a key value or not. Could be useful in some kind of lazy sorting.

In general, input would be useful.

a) What do you guys consider a) large nodes. b) small nodes. c) acceptable nodes.
(sizes, that is).

~zeii.

[elderK]

Also, its important to ask this...

How would you guys generally like your Heaps?
- Represented in an Array form?
(Will need a Dynamic Array, if you dont want to waste masses of space. Dynamic arrays are slow...)
- Represented through a Binary tree.

So far, I have completed:
- Binary Search trees.
- Singly / Doubly Linked lists.

All of them so far, do not do any Allocation. Removal is simply unlinking a given Node and returning its address, so you yourself, can deallocate it.

However, Dynamic Arrays will require Allocation / Deallocation. (To grow / shrink the Array).

Singly / Doubly Linked lists have no Key. Binary Search tree Nodes do have a key.

I didnt figure the Linked lists would need one, since you can create a Key value yourself.

eg:

Code: Select all

typedef my_sll_node_def my_sll_node_t;

struct my_sll_node_def {
  sll_node_t sll_control;
  uint32_t key;
}

In that Structure, the Key for the SLL Node is simply the Memory address of the entire structure. If youd like, You could track that Memory Address in the Key variable of said structure.

That being said, it wouldnt be difficult to expand the SLL / DLL to work with Keys.

So, this brings up another question. Do you want SLL/DLL nodes to have keys integrated, or not? Or would you simply write your own routine for Traversal?

~zeii

[elderK]

My work so far.
(I have done this in a super-rush job, free time. Oy, its a b*tch, I tellsya!).

No commenting, youll have to forgive me.
(Commenting will be included, when I have time...).

Structures:
- BST
- AVL
- DLL
- SLL.

No Allocation / Deallocation needed.

Things you should keep in mind:
- During Insertion (AVL and BST), if the Node you are trying to insert has an identical key to one already in the tree, it will simply return the Node address - just like the successful case. CHECK that your node has actually been inserted.

Normally, the routines would have deleted the Node. (Im trying to do as much here without relying on MM as possible.).

In all structures, removal simply unlinks the Node and returns it's address, so you, yourself can deallocate it.

All tests are done on the Stack, at the moment.
~zeii.

[elderK]

Well, Im making some minor modifications on the existing GLoom Lib before I continue and add more ADTs.

Mostly, Im just fixing how I deal with Identical key insertions.

Ill keep you all posted.

Feedback, suggestions, ADT requests, etc. Would all be appreciated.

~zeii

[Candy]

Is it OK if I branch your code at some point for my libstdc++?

[elderK]

Of course. ZCL Gloom is Public domain, so go right ahead!

Any improvements, I would appreciate the sourcecode being sent back, that way we can improve the Library.

Any structures you can add, would also be appreciated. At this time, Im learning about Redblack trees, so their implementation will take quite some time.

The sleepless,
~zeii

[elderK]

Sorry about the lack of updates lately people, Ive been remarkebly busy with University and somewhat annoying commerical obligations. Oh, and system failures. Ah, such fun.

Id like feedback on what ADTs would actually be useful to people. Id also like some help, if anyone is interested (Mainly on Redblack trees, since I am yet to learn about them).

Anywho, Just posting to let you folks know that the library is still alive and is still under development.

~zeii

[elderK]

Just thought id say ... Because of rush-University deadlines, ZCL Gloom is now much less buggy, WOOHOO!

Different AVL Removal methods, depending on requirements, depending on what you need.

Anywho, back to work. I have a deadline in 4 hours!

Wish me luck.

~Zeii, Midnight man.