Memory Manager, Garbage Collection, Recycle Bin, Defrag

[SpyderTL]

So, I've mentioned before, I think, that I had originally set out, seven years ago now, to build an OS that treated system RAM and hard drive space the same way, so that it could use common logic to do things like allocate and unallocate memory and clean up and defragment unused memory.

I've since learned that it's more difficult than I thought to treat all memory the same, mainly due to the block address nature of storage devices, the latency involved, and the fact that everything has to be first copied from storage into memory before it can be read.

But, this is still one of my goals, to the extent that it's actually feasible. I am now getting to the point where I am starting to think about a smarter memory manager (my current one just keeps a pointer to the next available memory address, and increments it as needed), and garbage collection. Since virtually everything in my OS is an object (essentially a struct, with a separate structure that describes the location and metadata of the struct), I am thinking about combining the memory manager and object manager/garbage collector into a single system, so that even simple memory buffers would be treated as objects, and the object structure that describes the struct / metadata could be used in place of memory tables. And objects that are no longer used can be stored in the "Recycle Bin" and reused in the future, instead of having to unallocate, reallocate and reinitialize them.

And, like your Recycle Bin on your hard drive, no clean up will need to be done at all, until you have used up all memory, and you need to start reclaiming old objects and repurposing them as new objects. And if all goes well, the objects in memory and the objects stored on disk will be stored and managed in the same way.

We'll see how well it goes. I'll be (slowly) implementing all of this stuff over the next few months. We'll see how close I can get to my goal of building a truly object oriented OS.

[tsdnz]

Hi,

And objects that are no longer used can be stored in the "Recycle Bin" and reused in the future, instead of having to unallocate, reallocate and reinitialize them.

How do you get around reinitalize?, Some of the properties might have changed.

And, like your Recycle Bin on your hard drive, no clean up will need to be done at all, until you have used up all memory, and you need to start reclaiming old objects and repurposing them as new objects. And if all goes well, the objects in memory and the objects stored on disk will be stored and managed in the same way.

I found that performance was better with out GC, saying this each of my OSes is custom built. Otherwise you will have to keep a list of all objects, more work and more memory to hold said list.

[embryo2]

to build an OS that treated system RAM and hard drive space the same way

It can be simpler on the higher levels, but if you want some performance then lower levels will be too complex. Or you can forget about performance. I doubt it is possible to write anything close to the simple side of the development universe using contemporary tools and treating everything in a similar way while still keeping good performance. For example - complex object hierarchies is the way of doing with different cases, but when the hierarchy grows the complexity just kills the idea of hierarchy and then the whole thing usually being split into separate entities.

May be you can use a front end layer that can hide the independent deeper levels from you and makes the picture to look simpler without the need for intertwined solution.

[SpyderTL]

How do you get around reinitalize?, Some of the properties might have changed.

There are two structures that have to be created (allocated and initialized) when creating a object. There's the object's internal data, which is pretty much just a type-specific struct, and there's the object "wrapper" that describes the object reflection meta-data (size, location, type, etc.).

Let's say that I'm reading a sequence of Employee records from a file. If there are 100 Employee records, and I read them one at a time, and store them in a collection, then I need 200 total structs in memory, until they are all garbage collected. But let's say that I'm not putting them in a collection, and I'm just rendering them to the screen. In this case, the callee would create (or ask the object manager to create) 2 structures (object and data), fill the data structure, and return the object structure to the caller, who would call, say, ToString to convert them to strings and draw those strings to the screen, and then get rid of the reference to the object (or explicitly put the object in the recycle bin). Then, the caller would ask for the next record from the callee, who would ask the object manager for a new object of the same type, but the object manager can now simply grab the object from the recycle bin, and return it to the callee, who would fill it up again, and return it. And so on.

This is sort of an indirect way of passing an object for the callee to fill, which is still an option, of course. But it's a little more flexible, because the callee can return a different type (subtype) than the caller is expecting, as long as the inheritance is maintained. By passing an object for the callee to fill, the callee is limited to only using whatever type it was sent.

So, either way will work, but the recycle bin is just a performance trick to keep from having to collect and reallocate every single object. It works best if the old object and the new object are of the same type, but it may still be worth it even if the type changes, as long as the data size stays the same (or as long as the new type is smaller...).

Think of it as an Object Pool, similar to a thread pool or a connection pool, where a bunch of "things" are pre-created and reused, rather than creating a new one each time one is needed.

I found that performance was better with out GC, saying this each of my OSes is custom built. Otherwise you will have to keep a list of all objects, more work and more memory to hold said list.

True. I haven't figured out how (or if) I want to keep track of every object at the OS level. That seems to be the most obvious solution, but I'm thinking about possibly letting the Applications keep up with their own objects, so that when an Application shuts down or crashes, all of its objects can be thrown away at the same time. But I'm still thinking through all of that. I'll probably just put everything in one giant collection, to start with, and see how that flies.

May be you can use a front end layer that can hide the independent deeper levels from you and makes the picture to look simpler without the need for intertwined solution.

Yeah, worst case scenario, I will be able to treat system RAM and storage device memory the same at the object level. But I just think it would be cool if the structures used to keep track of objects in memory and on disk are identical. We'll see...

[tsdnz]

True. I haven't figured out how (or if) I want to keep track of every object at the OS level. That seems to be the most obvious solution, but I'm thinking about possibly letting the Applications keep up with their own objects, so that when an Application shuts down or crashes, all of its objects can be thrown away at the same time. But I'm still thinking through all of that. I'll probably just put everything in one giant collection, to start with, and see how that flies.

My User OS I let the users do what they want with memory, they send pointers to kernel calls that populate the structs, this way they decide what is best for them. The hardest bit is the kernel allocating memory. Use bitmap = very fast, unless asking for large memory, AVL = fast until heaps of holes appear where rebalancing costs, linked list = fast sort of like bitmap. I found this the hardest decision, what will the end user use it for...

Then you have to think about DMA for things like NIC cards that use DMA not virtual addressing, so asking for 1 x Ethernet frame of lets say 1522 bytes cannot expand over different pages that are not continuous, if you allow direct Ethernet packet creation instead of memory copy. So it depends on what the memory is used for.

For me it was a great time thinking about it all and trying to figure out the best solution.

One design I hope to implement this year is memory connected from multiple servers all combined into one, using 10 GB NICs passing the data back and forth as the pages are required, this is going to be fun, it will require the programmer to have a good understanding of the system before programming to get the most out of the system.

Ali

[SpyderTL]

Okay, so I'm starting to lay out my new structures for my combination memory manager / object manager / garbage collector, and I'm starting to think about duplicating these structures on disk to use as a file system.

So, to start with, I am using 32-bit values as memory address pointers, and was planning on switching to 64-bit addresses if/when I ever decided to (seriously) support 64-bit mode. But now that I'm thinking about disk structures, now I'm thinking that at least the disk structures (if not both disk and memory structures) should use 64-bit addresses.

The reason for this is that I'm planning on, at some point, storing objects on disk at locations that are not block aligned, and which can be stored at any logical byte address, and have the driver do the legwork of translating addresses into blocks and offsets, etc.

So, the question is, has anyone attempted this and pulled it off. I know that obviously performance will take a hit, but I'm willing to take a small performance hit if the tradeoff is being able to use all of the storage space on the drive.

Also, as I am writing these structures out, it occurred to me that I can simplify the memory/object manager further by simply adding any free space found by reading the memory map to the Recycle Bin as generic objects. Formatting a disk would also be a simple matter of adding the entire disk volume, minus the structures I'm currently working on, to the Recycle Bin as a single large object.

On a related note, how much effort and space should I devote to preventing data corruption on disk? SSDs and USB flash drives seem to be pretty immune to data errors, while hard drives and floppy drives seem like they are very likely to lose data over time. Surely the answer isn't to store every file and structure in two locations, but that seems to be the only guaranteed solution to the problem, aside from using some sort of checksum that will allow me to attempt to rebuild the original data.

What options are there for data correction, and what are you guys using? I know that most existing file systems have some level of support for error correction, but I have no idea how they work.

[tsdnz]

So, to start with, I am using 32-bit values as memory address pointers, and was planning on switching to 64-bit addresses if/when I ever decided to (seriously) support 64-bit mode. But now that I'm thinking about disk structures, now I'm thinking that at least the disk structures (if not both disk and memory structures) should use 64-bit addresses.

I use 2 x 64-bit variables to store mine. Then compute what data-center, server, and storage device the data resides in. The user specifies the block size, 512, 2048, ....

The reason for this is that I'm planning on, at some point, storing objects on disk at locations that are not block aligned, and which can be stored at any logical byte address, and have the driver do the legwork of translating addresses into blocks and offsets, etc.

Myself I prefer block aligned, much easier to program and I am willing to lose a little disk space if needed.

So, the question is, has anyone attempted this and pulled it off. I know that obviously performance will take a hit, but I'm willing to take a small performance hit if the tradeoff is being able to use all of the storage space on the drive.

I have written test code for both. I found block alignment much faster and only minimal disk space lost, and the code is much cleaner and much easier to handle block locking, etc, if you use the ports, which I found annoying that they combined the ports into one 32-bit register as this sets a requirement to have a "lock" on the register.

Also, as I am writing these structures out, it occurred to me that I can simplify the memory/object manager further by simply adding any free space found by reading the memory map to the Recycle Bin as generic objects. Formatting a disk would also be a simple matter of adding the entire disk volume, minus the structures I'm currently working on, to the Recycle Bin as a single large object.

Not the way I do it, but it sounds like fun.

On a related note, how much effort and space should I devote to preventing data corruption on disk? SSDs and USB flash drives seem to be pretty immune to data errors, while hard drives and floppy drives seem like they are very likely to lose data over time. Surely the answer isn't to store every file and structure in two locations, but that seems to be the only guaranteed solution to the problem, aside from using some sort of checksum that will allow me to attempt to rebuild the original data.

For me data corruption/duplication is specified by the user. Basically my storage OS is like a RAID controller, it can split and/or duplicate the data over many data-centers. It is possible for a user to specify 7 duplications across different data-centers, this might increase once I start coding deeper into it.

What options are there for data correction, and what are you guys using? I know that most existing file systems have some level of support for error correction, but I have no idea how they work.

I am hoping to give my storage OS more time in the coming year, this is something I am also interested in, so far mine is just relies on the hard-disk error reporting and will use duplication if user specified it.

Ali

[Brendan]

Hi,

Okay, so I'm starting to lay out my new structures for my combination memory manager / object manager / garbage collector, and I'm starting to think about duplicating these structures on disk to use as a file system.

As far as I can tell; you don't understand what you're doing.

Forget everything you think you know, forget about objects (for now) and forget about files and file systems (for now).

Imagine you have a virtual memory layer. Normally (for a traditional OS); each virtual page has something backing it (e.g. a page of physical memory or a block on disk somewhere). For a persistent store; each virtual page always has something on disk backing it (regardless of whether there's a copy in physical memory or not). In this case physical memory is used as something like a "write-through disk block cache".

In this way you have persistent virtual pages. If the computer loses power, you just load the virtual pages from disk again.

After you have persistent virtual pages (or persistent virtual address spaces) working; then you implement whatever you like on top ("objects"). Because objects are stored in persistent virtual memory the objects are persistent. The physical memory manager, storage device manager, etc have no reason to know or care what an object is; because that's too high level for them (they only deal with physical pages or disk blocks).

If you have persistent objects then you don't really need a file system. For example; you can give all the objects names, and you can have a "container object" called "foo" that contains references to 123 other objects, where one of those objects is called "bar" (and this would behave like a file system where "foo" is a directory and "bar" is a file within that directory).

Essentially what you've got is a hierarchy of objects in virtual memory; where neither physical memory manager nor storage device drivers have any reason to care that it exists and still only deal with pages/blocks.

The performance problem here is "physical memory is used as something like a write-through disk block cache". Every time any CPU writes to anything, you need to write that data back to disk. Obviously this would completely destroy any hope of acceptable performance; so you need to "cheat". If you do "physical memory is used as something like a write-back disk block cache" then you lose any changes that have been made but haven't been written back to disk; and this leads to corruption (e.g. references that were stored on disk, that refer to something that wasn't written on disk) which leads to failure.

You need something that avoids the "all writes cause disk IO" problem that is able to guarantee that everything on disk is consistent. The simplest method is postpone all writes to disk as much as possible; then (when you have no choice); freeze everything, then "atomically" update everything on disk at the same time, then allow things to continue. Essentially, you'd be (periodically) taking a snapshot of all virtual memory contents; and if there's (e.g.) a power failure you lose any changes made after the latest snapshot, but everything is guaranteed to be consistent when rebooting (booting just restores everything to the state it was when the snapshot was taken). Of course "freeze everything" is unlikely to be fun either. That's where things get tricky.

On a related note, how much effort and space should I devote to preventing data corruption on disk?

Probably none. It'd be better to handle data corruption prevention at the highest level (and not bother at lower levels) - that way it'd guard against things like RAM corruption too.

SSDs and USB flash drives seem to be pretty immune to data errors, while hard drives and floppy drives seem like they are very likely to lose data over time.

SSD and USB flash have "wear" (and wear levelling logic to try to compensate). When they're new they're very reliable; and after a few years (depending on quality, how often you're writing to it, etc) they become extremely error prone. There's also very few SSDs that have full power loss protection - for most of them, power loss at the wrong time can cause data to be corrupted, even data that isn't being read/written at the time, and even when you're not reading/writing anything (because they do things like internal de-fragmentation when idle).

What options are there for data correction, and what are you guys using? I know that most existing file systems have some level of support for error correction, but I have no idea how they work.

There's always (software and/or hardware) RAID; but that doesn't prevent problems that happen "higher up" (e.g. if data is corrupted between an application and the RAID controller).


Cheers,

Brendan

[Rusky]

On the other hand, a persistent store that knows nothing about what it contains can't really guard against things like power failure. A file system at least knows where the metadata is vs where the file contents are and can control the order of updates, to make it easier to recover when something does go wrong.

[SpyderTL]

As far as I can tell; you don't understand what you're doing.

That's a fair assessment.

Imagine you have a virtual memory layer.

Okay, let me go ahead and stop you there. I think I have a pretty good understanding of virtual memory and paging (although I've not really implemented either, yet), but that's not really what I was talking about.

I'm not trying to extend system RAM by using hard drive space. I'm trying to write a combination memory manager / object manager / garbage collector in a way that the exact same code can be used to keep track of objects stored in system RAM and objects stored on a storage device.

Most operating systems support virtual memory with automatic paging to a swap file, but I'm shooting for something different. I want to be able to boot up in less than a second, and then I want to use my PC to do all of my typical daily routine without ever touching the hard drive again, at least until I explicitly load or save something from/to disk. So, if everything that I want to do happens to be in memory, I can put the hard drive to sleep, and it will stay that way until I wake it up. I want to have full control over which devices are active, and which devices are inactive. If I know that I won't be needing the sound card today, there's no reason for the OS to load drivers for it, initialize it and constantly communicate with it in the background.

I will probably implement virtual memory at some point, when I actually want to run an application in a safe environment, in order to keep it from affecting the rest of the system, but for now, everything I want to do is supported by the built-in objects that are included with the OS. But I doubt that I will implement paging to disk any time soon. It pretty much represents the opposite of my end goal.

[tsdnz]

I want to be able to boot up in less than a second

How long does it take to boot your OS?

[SpyderTL]

I want to be able to boot up in less than a second

How long does it take to boot your OS?

Pretty much instantly. On a floppy it may take a few seconds. I haven't had a physical machine with a floppy to test on in probably 8 years. I think I may have one up in the attic...

To be fair, though, my entire OS currently takes up about 720K, and that's with all 276 loadable objects being block aligned, and loaded one at a time by the boot loader, so there is some wasted space in there. I'm not sure if I want to package all of the objects together in a single file that can be loaded with a single call, or if I want to load just the few objects that I need to get started, and load the rest of them on demand at a later time...

When VirtualBox first added support for capturing video, I uploaded a quick session to YouTube to show off exactly how the system currently works. There are a lot more features, now, but it should give you an idea of how fast it boots from a virtual hard drive.

https://www.youtube.com/watch?v=f-KMbNpJ2Jk

It's currently text mode console only, although I do have another project that I've started that is GUI based. I'm planning on merging them together at some point.

Currently, I've got the following features (somewhat) working:

• Play 44100 stereo audio streams to SoundBlaster, AC97 and HD Audio devices. (Not terribly stable, at the moment)
• Render 3D triangles to VMWare SVGA accelerated video card
• Connect to network and request raw HTTP pages from any web server on the internet. (VirtIO network devices only, at the moment.)
• Read files from FAT32 and CDFS file systems
• Read raw data from floppy disks, IDE Hard Drives, IDE CD Drives and USB Storage Devices
• Read WAV audio data from Audio CDs
• Calculate integer math, floating point math, and vector and matrix transforms.
• Scheduling tasks on a single processor
• Initialize and Startup all AP processors (new)

I need to get a new CD image build up on the CodePlex site at some point, but the old image should have most of these features working.

[tsdnz]

https://www.youtube.com/watch?v=f-KMbNpJ2Jk

Nice video. Makes it easier to see what you are trying to do.
I guess everything is an object with a meta header with properties etc?

[Brendan]

Hi,

I'm not trying to extend system RAM by using hard drive space. I'm trying to write a combination memory manager / object manager / garbage collector in a way that the exact same code can be used to keep track of objects stored in system RAM and objects stored on a storage device.

What are "objects stored on a storage device"?

Conceptually, an object is "code + data". Are you storing an object ("code + data") as a single thing on disk?

Often in practice an "object" isn't actually a true object because code is separated from data (the object's code is a "class" shared by all objects of a specific type). In that case; what is the difference between storing the class' code on disk (as an executable file) and storing each object's data on disk separately (as a data file)? How is this different to a traditional file system?

For both of these cases ("true objects" and "just glorified files"); what happens when the object is modified (e.g. a "setter" method is used) when the object is on disk?


Cheers,

Brendan

[SpyderTL]

https://www.youtube.com/watch?v=f-KMbNpJ2Jk

Nice video. Makes it easier to see what you are trying to do.
I guess everything is an object with a meta header with properties etc?

Yep.

Conceptually, an object is "code + data". Are you storing an object ("code + data") as a single thing on disk?

All objects have data located in one location, and metadata located in another location. (.NET combines these into a single location, and stores the metadata right before the object data, which I may decide to do at some point..) The metadata has a pointer to the actual data, and a pointer to a class object. The class object metadata has a pointer to the data (which is filled with code and more metadata describing the methods and properties), and a pointer to a base class type object that acts as the base type for all classes. And that object has a base type of Object, which is another class.

Often in practice an "object" isn't actually a true object because code is separated from data (the object's code is a "class" shared by all objects of a specific type). In that case; what is the difference between storing the class' code on disk (as an executable file) and storing each object's data on disk separately (as a data file)? How is this different to a traditional file system?

It's not terribly different, but the biggest difference would be the metadata, and the complete discarding of the "file" paradigm. As I've mentioned before, the File/Folder terminology makes sense in some cases, but in other cases, it really makes it difficult for the user and the application developer. The best example I can think of is Music. I've got thousands of songs on my PC, and I have spent countless hours organizing them into a folder structure that makes sense to me. But as soon as I run an application to play that music, it has its own idea how things should be organized, and I have to prevent it from moving things around. Also, if my daughter wants to use the same PC, but wants the same songs organized differently, then the file system is completely useless.

So, I'm shooting for something not quite like a traditional file system and not quite like a traditional database. The plan, for now, is to store everything on disk as an Object of some sort, and then add additional Indexes (which are just objects) that will allow you to find objects of a specific type, or that have a specific property value, like where the song artist is equal to "The Eagles".

Most operating systems have built this sort of functionality on top of their file systems, and most applications have built additional functionality to make this all possible. I'm just trying to cut out all of those layers, and build all of that functionality directly into the OS and the storage structures, so that all of this information and functionality is available immediately at boot time from the command line.

For both of these cases ("true objects" and "just glorified files"); what happens when the object is modified (e.g. a "setter" method is used) when the object is on disk?

Still working out the details, but most likely modifying a property on an object (either in memory or on disk) will involve simply changing the value, externally. But internally, it would involve asking the OS for a "Writer" object for that property, and then calling .Write(newValue) on whatever it returns. For objects in memory, you would get a memory writer pointing directly to the memory location, and for objects on disk, you would get (for lack of a better term at the moment) a file system writer, pointing directly to the offset of that property on disk.

Of course, a lot of things have to fall into place for all of this to work properly, but it all works great in my head...

Properties that contain references to other objects is going to be particularly tricky, since the value will be different in memory than it would be on disk, so that will probably involve finding (or creating) a corresponding object on disk, and using a reference to that object, instead of the original object. I may ultimately need to assign each object a GUID in order to keep track of object instances that are located in memory and on disk at the same time.

EDIT: I uploaded a fresh set of bootable images to CodePlex. If you want to check it out, just click the link in my signature.