OSDev.org

This somewhat furthers the thread I made a couple of weeks ago about a low-level Lisp dialect.

I'm sure I'm not the only one who doesn't like manual memory management. Languages with garbage collection have been shown many times to improve productivity for that very reason. However, we in the osdev world can't easily construct a garbage collection system, because that would require language support, and a common language that has GC would force that requirement on everyone. Otherwise, we probably would all be using GC. But maybe low level memory management is not the problem. While trying to figure out a good way to do manual memory management in a Lisp-like language, I think I came up with a better and cleaner way of doing it in general.

The basic idea is this: memory management should not be thought of as a series of allocations and frees, but instead of the movement of a data structure from temporary to permanent position. If the structure is allocated on the stack, it is temporary, and does not need to be worried about for memory leaks; it will be freed when the function returns. If the structure is allocated in the heap, it is permanent, and can be moved out of functions without being freed. GC is just one step of abstraction above this model - temporary vs. permanent is decided automatically.

The design is composed of two complementary functions: loc() and glo() (short for localize and globalize).

The glo() function takes a pointer and a size, and returns a pointer to an area of memory on the heap that contains exactly what the pointer given to it did. If the pointer given is already in the heap, it is passed right back.

The loc() function takes a pointer and a size, and returns a pointer to an area of memory on the stack that contains exactly what the pointer given to it did. If the pointer given is in the heap, it is freed. If the pointer given is on the stack, it is still copied. loc() would probably be a macro that uses alloca() internally in C.

This in heap/not in heap detection requires some support from the libc or whatever implements the heap, but those extensions are very straightforward: only one range needs to be checked - double frees would not need to be detected. In the language I designed, pointers have implicit size attributes, which makes the syntax cleaner, but it could still be done in C quite well.

As you can see, there is a sort of conservation of information between these functions. The general pattern would be to allocate a structure as a local variable, initialize it, then set a pointer in the larger data structure to the glo() of it. Freeing doesn't have to be done after all manipulation either: when a structure is detached from a larger data structure with loc(), it can still be read and written before the function ends, which is imo more intuitive and less likely to cause an accidental leak than saving the pointer to free at the end.

Of course, this comes at the cost of a lot of memory copying, so it wouldn't be as fast as malloc() and free(), especially for large allocations - that's why it can't replace them entirely. However, I believe that this clean, intuitive, no-special-case design would be a reasonable advancement of the usual C WYSIWYG manual memory management. There is no need for additional library or language support, except a simple addition to the libc, to do it either.

Questions? Comments? Ideas for making this better?

I respect your efforts in attempting to find a better way, but I really don't see the advantage in this. The major disadvantage of your method is one that you already mentioned, the constant mass memory copying will cause huge slowdowns over conventional malloc()/free(). This slowdown would actually be orders of magnitude larger than the decrease in efficiency that garbage collection causes. Not only that, but this really doesn't offer any improvement. With having two calls to explicitly change things to/from freeable status, what is the benefit over using those same two lines to allocate or free a resource?

Honestly, the closest I can come to thinking of a suggestion would be to just use a reference counting system, which achieves part of your goals, but I don't think that's quite what you're looking for.

It is true that the copying would slow down allocations quite a bit, but for small allocations (16-64 bytes), like for structures used as trees or linked lists, the penalty would probably be dwarfed in comparison to the action of the heap. Not to mention that those things have to be initialized one way or another, so the copying is at least not redundant. Even for large arrays, at least one pass of initialization of some sort happens, and when more speed is needed, malloc()/free() are fine to work with and compatible with these additional interfaces. I would not expect huge slowdowns, but I would have to run real world tests to know for sure.

There are a couple of ways I think this design makes an improvement. First of all, it gives a much more functional (as in the paradigm) interface to memory management, because allocation and freeing act almost like transformations of data, instead of sources or (more importantly) sinks. In the language I am designing, this is very beneficial to the clarity of functions, because it is a semi-functional language. The design also increases the abstraction in allocation - glo() doesn't explicitly allocate, it just guarantees the argument has been allocated; loc() doesn't explicitly move to the stack, it just guarantees the argument is in the current stack frame. This way, you don't have to care what the structure's state was, only what its state will be, which means no double-frees, no double-allocations, and few special cases. This would otherwise have to be done explicitly at every allocation.

I realize that garbage collection (reference counting) is a good idea for most circumstances, but my goal is low level system programming, where garbage collection is not possible due to language constraints (higher level languages are possible, but require rewriting the runtime in C/assembly anyway).

All right, I can see that. There was another piece to my logic that I somehow failed to add, though. If you're already explicitly marking things, why can't you just have a primitive form of garbage collection? Why not just have these marking calls change their state in some metadata? You could do something similar to Objective-C method calls and just have function calls go through the runtime so that, say, on function return, the collection routine goes through and frees everything marked freeable? Or even have it keep a simple count so that it does this every n-th function return, to reduce overhead, like clock ticks->scheduling. That's definitely overhead, but less overhead than the copying.

I knew I meant for something in my first post to be constructive, sorry for waiting for the second post.

EDIT: I don't know all the circumstances, but this solution seems all the more practical in that you're designing your own language. You don't even have to use something like a FUNCTIONCALL(func)(the, arguments) macro to make the calls go through the runtime.

The programming language of my own design employs forms of aspect-oriented programming, which allows optional garbage collection code to be woven into code, without forcing the compiler to understand it.

If only I had time to write a compiler for that...

@inx:

Nothing is being marked when these calls are performed. The way it's decided whether the pointer is in the heap or not is whether it is between the base address of the heap and the current end address of the heap. It's only conceptually being 'marked' by being moved from the stack to the heap or vice versa.

The functions would be similar (but not the same) to these macros: Of course, the logic for freeing and checking the type of the pointer are not possible in macros with standard functions, but the idea is there. It is really not much more than a wrapper, and doesn't change the data or keep any metadata.

(Tangential rant, ignore at will.)

NickJohnson wrote:I'm sure I'm not the only one who doesn't like manual memory management. Languages with garbage collection have been shown many times to improve productivity for that very reason.

Yes, because >95% of programmers worldwide are the digital equivalent to unskilled labor, pushed into the market by the huge demand for cheap-code-quick (aka code monkeys).

In my book, picking up OS Dev pretty much requires you to be of the remaining <5%, and in my experience, those have no problem handling their pointers. We are working with CPU flags and memory-mapped devices, in a realm of precise control, not of couldn't-I-click-this-together-with-a-wizard.

Otherwise, we probably would all be using GC.

Erm... -1.

If I would want to work in an environment where simple tasks (like getting malloc() / free() right) were taken from my hands, I would write a user application in Java. If I were worried about time-to-market, I'd probably write an iPhone app or a flash game that can be done within a week. But I chose OS Dev, because I like to go down to the detail, take my time, and build a thing of crystaline beauty.


Sorry, had to get this out of my system.

Solar wrote:Yes, because >95% of programmers worldwide are the digital equivalent to unskilled labor, pushed into the market by the huge demand for cheap-code-quick (aka code monkeys).

In my book, picking up OS Dev pretty much requires you to be of the remaining <5%, and in my experience, those have no problem handling their pointers. We are working with CPU flags and memory-mapped devices, in a realm of precise control, not of couldn't-I-click-this-together-with-a-wizard.

I totally agree, but just because we, in the "remaining 5%" can use straight manual memory management proficiently, doesn't mean that it is the best thing to do in all situations. Being in the top 5% means that you have the ability to choose how to do things, not that you have the responsibility to do it the hardest way. I'm fine with any high level construct that does not sacrifice the precision and control needed to do what I want it to. I generally don't care either way with GC, as long as the environment makes it tractable, and my idea really has little to do with it - I was just using it as an example to explain the concessions about manual vs. automatic memory management to introduce why I was thinking about it in the first place. I doubt any programmer unable to use malloc() and free() would be able to use glo() and loc(), but those able to use both should be able to write more concise programs.

NickJohnson wrote:Nothing is being marked when these calls are performed. The way it's decided whether the pointer is in the heap or not is whether it is between the base address of the heap and the current end address of the heap. It's only conceptually being 'marked' by being moved from the stack to the heap or vice versa.

That was kind of my point. You're making the memory bus go through all of this effort to move things and doing a bounds check on every object to create a logical marking out of something unnecessarily corporeal. Why? Those same calls could provide the same functionality *with* metadata and be an insane amount faster. This comes back to what Solar was saying: If you want everything to be easy for an unskilled human to understand at the sake of being beyond inefficient, why is this going in OS code? At least a garbage collected language for some user app would be massively more efficient.

I see your point now. I did some benchmarks using glibc, and the memory copying increases the runtime by 15% with only 64 bytes, using -O3. -O0 nearly doubled it.

I've also figured out an equal but more flexible way of making this interface in the new language, which doesn't force the copying of data. It uses the existing memory-copying operators with the normal malloc() and free() calls.

NickJohnson wrote:I've also figured out an equal but more flexible way of making this interface in the new language, which doesn't force the copying of data. It uses the existing memory-copying operators with the normal malloc() and free() calls.

Sounds like a good plan.