10 ms·
On programming without malloc
- dradtke 13y agoI'm really looking forward to Rust 1.0. It seems like an awesome language in many respects, not least of which because it's possible to write operating systems and other low-level software in, but the lack of stability will be kind of annoying for a while.
- angersock 13y agoAh, good ol' malloc. You are wise to implement malloc once...you are a fool (or a masochist) to implement it twice.
- tomlu 13y agoI've implemented it thrice. Easy to get working, surprisingly tricky to balance all the space/performance requirements. You do get better at it!
- adam-f 13y agoA neat trick (tm) for allocating a linked list: recursively call a function which allocates a node on the stack, hooking them up in the function... call something else and pass the list to it. at the exit condition (whatever that is), exit the recursion and call something else with your new linked list. (I used something similar to keep track of scope while recursively evaluating in this toy language I made once.)
- jvanenk 13y agoA friend of mine wrote something up on this technique a while ago: http://spin.atomicobject.com/2012/11/01/hey-c-is-a-functional-language-too/ http://spin.atomicobject.com/2012/11/01/hey-c-is-a-functiona...
- justinhj 13y agoThe book Modern Compiler Implementation in C has a very functional style, written in 1997
- silentbicycle 13y agoThere are editions of the book using ML and Java. Since Andrew Appel is involved with SML/NJ, the ML edition is most likely the original. (The ML one is also quite good.)
- apgwoz 13y agoIsn't this just a simplified version of Cheney on the MTA? (http://home.pipeline.com/~hbaker1/CheneyMTA.html http://home.pipeline.com/~hbaker1/CheneyMTA.html)
- adamnemecek 13y agoOT but I've never seen anyone write semicolons that way in C.
- jonhohle 13y agoCommas? Personally, I'm never a fan of punctuation first formatting styles - though I give some exception for dot (.) first method calls in fluent interfaces for C-family languages. someInterface .thatCan() .chain() .itsCalls();
- adamnemecek 13y agoYeah, commas.
- asveikau 13y agoThis is kind of bad to do in a kernel. It is up to you to map the pages of your own stack. Once you have higher level concepts like a process, it's fair for the kernel to look at that state from a privileged position and say "OK, I will allocate more stack pages as it faults, and kill the process if I fail or it goes too far". But for kernel mode code, that last part could lead you to a scary place. IMO it's better to just use a few pages for stack and not go crazy with recursive functions.
- tjdetwiler 13y agoPlus if you have your kernel stacks allocated in the same virtual address space, you might not be able to just "grow the stack" since that memory may be in use. But yes recursion in a kernel is a "bad thing" unless you know the recursive bound.
- anon4 13y agoI imagine you basically mean that the called function stack-allocates one list node, sets up a "return trampoline" so when a return is executed, the returned value is returned one more level up, then jumps back into the code that called it. The issue I see is that returning gets to be a somewhat more expensive operation due to having to return several levels up. Am I completely wrong here?
- goldenkey 13y agoDoes Rust not have dynamic heap allocation (malloc)? An explanation to accompany the article would be nice. Or at least a comprehensive response to my comment ;-)
- cespare 13y agoRust uses malloc provided by the system. It's mentioned in the article: "I actually do have a malloc function because my Rust standard library needs to link against it" He hasn't implemented malloc in his kernel yet (except for a stub).
- rubyn00bie 13y agoShe actually (Julia Evans)! I just want to point that out since women don't get enough cred in our field.
- deleted 13y ago[deleted]
- cespare 13y agoThanks, I'm not sure how I got that wrong. I certainly registered that it was a woman when I read the article.
- kibwen 13y ago> Rust uses malloc provided by the system. It doesn't lock you into the system allocator. You can LD_PRELOAD your own, and in the past Rust has even shipped with and used jemalloc[1] (though I believe it's not using it at the moment). Furthermore, as alluded to at the end of the article, you can override the compiler's malloc implementation via what Rust calls "lang items" (which are sadly ill-documented). > He hasn't implemented malloc in his kernel yet (except for a stub). Rather, Julia hasn't implemented malloc in her kernel yet. [1] http://www.canonware.com/jemalloc/ http://www.canonware.com/jemalloc/
- pekk 13y ago
- majke 13y agoInteresting. Golang _runtime_ requires malloc, so even if used carefully I doubt you could use go in this way.
- apgwoz 13y agoBut, malloc doesn't have to be significantly advanced. In a situation where you have a large chunk of memory unallocated, the simplest thing to do is just to "bump" allocate it. Freeing it is a bit of pain of course, but you could build a freelist out of the chunks that are free. So, the suggestion looks like this: struct freemem { int len; char *addr; struct freemem *next; }; // globals int total_mem_size; char *start_of_memory; char *bump_pointer; struct freemem *freelist; Allocate is simply: if bump_pointer + MIN(size_to_allocate, sizeof(struct freemem)) < total_mem_size: int *b = (int *) bump_pointer; *b = MIN(size_to_allocate, sizeof(struct freemem); return b + sizeof(int) else iterate over freelist, checking for size_to_allocate < freelist->len return freelist->addr (the *b business is already taken care of) Deallocate simply turns the discarded memory into a struct freemem and prepends it to the freelist, setting addr = the discarded address, and len = *(addr - sizeof(int)) (it's for this reason that we allocate a minimum size of sizeof(struct freemem)) That's a basic malloc / free.
- apgwoz 13y agoUrr.. That should have been MAX, not MIN.
- munificent 13y ago> Freeing it is a bit of pain of course, but you could build a freelist out of the chunks that are free. If you want a much longer explanation of this technique, I wrote a chapter about object pools[1] that discusses exactly this[2]. [1] http://gameprogrammingpatterns.com/object-pool.html [2] http://gameprogrammingpatterns.com/object-pool.html#faster-particle-creation
- pcwalton 13y agoThat's one of the main reasons we say Rust and Go aren't in the same space (and that is not a knock against Go, their choices made a lot of sense for their domain).
- a-priori 13y agoThe simplest allocator ever is this: void *malloc(int size) { static long nextAddress = BASE_ADDRESS; void *ptr = (void *)nextAddress; nextAddress += size; return ptr; } void free(void *ptr) { return; } Using that will last you a long time in writing a toy operating system kernel. Of course, it will eventually run out of memory pages, but that shouldn't happen until your system has been running for a long time.
- deleted 13y ago[deleted]
- ricree 13y agoThere's a reason he said toy.
- __david__ 13y agoIsn't that effectively sbrk()?
- IgorPartola 13y agosbrk() does allocate memory of the size you want. Instead it allocates memory in chunks of the size of the system page. Thus, if you want to allocate a few bytes, you will get something like 4 KB instead, which is wasteful. Also, sbrk() is a syscall, so it's not available in OP's use case: he has not implemented it.
- alecdbrooks 13y agoThe author of the post is actually a "she," not a "he." I hate to be pedantic, but I think it's important to not assume authors of technical posts are men.
- mnbvcxza 13y agoOr we could just assume that 'he' means 'he or she'.
- kyork 13y agoI write C code for embedded devices and haven't been able to use malloc in 6-ish years. Everything is either statically or stack allocated. It changes how perceive memory usage and allocation. For example, it used to bug me that I had to statically allocate memory to manage an event that was used for maybe 0.1% of the product's life. It seemed so inefficient. Yes, you could potentially co-opt the event and use it elsewhere, but then you had to deal with a bunch of other considerations: could they ever run at the same time?, would the code be maintainable?, etc. Or the other day I accidentally set a function scoped buffer's size too large and it cause a stack pointer overflow. That was a pain to debug, because the exception happened "before" the function started running (in the function call preamble). From the debugger, it looked like the return of the previous function caused the issue.
- acuozzo 13y ago> I write C code for embedded devices and haven't been able to use malloc in 6-ish years. Where do you work?
- yitchelle 13y agoAnyone doing embedded code that is pretty close to the metal will have to avoid using malloc. I also write C code for embedded devices and also haven't use malloc for the past 15 years.
- kyork 13y agoI work for a home/building automation company. Primarily I write code for Zigbee wireless devices.
- leeoniya 13y agoa bit off-topic, but Zigbee came up in a discussion with a friend recently when talking about adding wifi functionality to PLCs. he mentioned that Zigbee devices are pretty much unusable in existing Wifi deployments because they run over the same bands/frequencies. can you comment on this at all? thanks!
- 13y ago
- MrBuddyCasino 13y agoA bit OT, but this is the first time I've heard about Hacker School. Is it as awesome as it sounds? If I wanted to join, how much money would I need to stay in New York for 3 months?
- jvns 13y ago> Is it as awesome as it sounds? Yes. > How much money would I need to stay in New York for 3 months? About $1000/month for rent, give or take, and $112 for a metrocard. Plus whatever you spend on food (depends how much you cook) and entertainment.
- jamii 13y agoDepending on the level of comfort you are used to, you can go a lot cheaper. I shared a room in Bed-Stuy for $350 / month and biked to Hacker School. I did then blow the money I'd saved by eating out every day, but that's a different matter.
- kybernetyk 13y agoOh, after your comment I read their about page. It really sounds awesome and is something I would be very interested in. I don't know why but I always assumed it was yet another "we teach non programmers some javascript"-programme. But it's really the opposite.
- jlongster 13y agoI've been working on LLJS and the current version (which targets asm.js) doesn't implement dynamic allocation yet. I've been making all kinds of demos without malloc and it has been surprisingly fun!
- sliverstorm 13y agoConsidering how much memory modern machines have, and considering she is running no other programs, I would be so tempted to write malloc like this just for grins: int malloc() { return rand() % TOTAL_MEMORY; }
- jvns 13y agooh man that is the kind of bad idea that I love. I'm definitely going to try implementing malloc that way and report on the results =D
- TheLoneWolfling 13y agoMinor qualm: is rand defined?
- apgwoz 13y agoWell, rand can be defined as a Linear Congruential Generator (https://en.wikipedia.org/wiki/Linear_congruential_generator https://en.wikipedia.org/wiki/Linear_congruential_generator), or some other well known algorithm. LCG's don't require anything that the machine doesn't already do (mod, addition and multiplication)
- rca 13y agoYou could use rdrand if you're on (a recent enough) x86. You just lose some portability. Probably not a major issue at this point.
- munificent 13y agoYou jest, but you'd actually get surprisingly far just doing: void* malloc(size_t size) { static void* everything = 0; void* result = everything; everything += size; return result; } When people are hacking together VMs for garbage collected languages, the first allocator often looks like this until they get around to actually collecting the garbage.
- apgwoz 13y ago
- gz09 13y agoIf you don't want to use malloc in a kernel, that is fine. However, you should at least consider having something similar. This can be as simple as finding the available memory in your system and writing a frame or slab allocator. It will make your life much easier. It would be interesting to see how easy it is to integrate your memory manager directly with the rust language.
- asveikau 13y agoWhen I was working on a hobby kernel, I'll confess I just took dlmalloc and called it a day. There are loads of interesting problems in kernel development (mapping pages, doing crazy stuff in page fault handlers, synchronization, filesystems) but somehow I didn't find malloc to be one of them. I guess anyone reasonably skilled at C can write a bad malloc pretty quickly, and once you get to that point you don't really learn that much by putting more effort into it.
- steveklabnik 13y agoYup, malloc is usually a homework assignment in the upper-level CS classes in my university. I wrote it then (and again for my friends' hobby kernel) but I couldn't do it now.
- joosters 13y agoThere's a huge depth to a good malloc() implementation. While you're wise to avoid it when your interests are focused on kernel development, I'd recommend every programmer to have a go at writing malloc/free one day. Avoiding terrible performance problems is pretty tricky. At the very least, you'll gain a lot of respect for memory allocation and will discover that there's a lot of work going on behind the scenes when your code tries to allocate only a few bytes of memory.
- exDM69 13y agoVery nice post! It takes special character to be working on your own OS kernel project, even a very simple one. Using Rust makes this even more interesting, because you have to know the language quite well to be able to avoid the parts that require runtime support. Programming without malloc is a good exercise and can also be valuable outside of kernel space. Computer programs written in a naive manner may end up spending most of their time doing memory allocations. This seldom happens in C programs because usually you're aware of every malloc you do. But I've had a few Python programs end up uselessly slow because of the time wasted in allocating small objects. I was doing some physics simulation prototyping with Python and the result was too slow to do work in (soft) realtime. (although you can avoid this, you'd be writing non-idiomatic Python code and that practically destroys any benefit of using it for prototyping). @jvns: do you have the source code of your mini-kernel project shared anywhere? Any plans for the future? https://github.com/rikusalminen/danjeros https://github.com/rikusalminen/danjeros this is my hobby kernel project from a few years ago.
- jvns 13y agoRight now it's a fork of rustboot [1], a proof-of-concept repo for implementing a kernel in Rust. I'm working on extending rustboot [2] to support handling keyboard interrupts and to have a real print function. It's not remotely in a working state yet, but I'll definitely update my blog when I get keyboard interrupts working. [1]: https://github.com/charliesome/rustboot https://github.com/charliesome/rustboot [2]: https://github.com/jvns/rustboot https://github.com/jvns/rustboot
- jvns 13y ago> you have to know the language quite well to be able to avoid the parts that require runtime support. This isn't really true, it turns out :) I've only spent about a week using Rust. I spend a ton of time in #rust asking questions, and everyone's been really helpful. The maintainer of rust-core (the library that lets you not require runtime support) hangs out in #rust all the time and has been wonderful about answering all my questions about it.
- 13y ago
- sixbrx 13y agoI've found Rust to be great at avoiding allocations. You can return a pre-allocated buffer to be shared by all callers from a function in a safe way that prevents interference between callers. The callers only get to keep it for a limited time (region, actually), but usually that's no issue. In exchange, the callers are gauranteed that the returned buffer contents can't be modified by any other part of the program while it is borrowed. Here's some code for multiplying some polynomial vectors which uses this style, without allocating (except for a single initial allocation of the buffer): https://github.com/scharris/WGFEM-Rust/blob/master/weak_gradient.rs#L275 https://github.com/scharris/WGFEM-Rust/blob/master/weak_grad... Line 275: The structure holding the buffer and on which the operations are implemented. Line 287: the buffer field Line 297: The operation returning a structure (by value) which has an immutable "borrow" of the shared buffer. It's lifetime is tagged with lifetime 'a, tied to the lifetime of the implementing object. Line 319: The buffer being included in the return value. I really like the pattern. Get the efficiency of not allocating, kindof like old school libraries like LAPACK, without doing things like writing over your inputs :)
- optymizer 13y agoImplementing malloc() was one of the first assignments in my OS class. A linked list with some header information about each allocation will get you a long way before you need a better algorithm.
- ww520 13y agoMemory allocation in kernel needs special care. Usually the plain malloc() is not enough, once interrupt and memory paging are in place. Since your piece of the kernel code can run in different interrupt level, you really need a pageable memory allocator and a non-pageable allocator. At a high level interrupt (like hardware interrupt), the memory paging service won't get a chance to run and accessing a pageable memory might crash the system. You want to allocate non-pageable, pinned down memory for your code that runs in high interrupt level. For low interrupt level code, it's fine to use pageable memory. That's why kernel mode development is a lot more difficult and fun.
- e12e 13y agoHm, is there a reason why you've not declared something like "const VGABUF: int = 0xb8000;" (like I assume VGA_WIDTH is defined?)? pub unsafe fn putchar(x: u16, y: u16, c: u8) { let idx : uint = (y * VGA_WIDTH * 2 + x * 2) as uint; // 0xb8000 is the VGA buffer *((0xb8000 + idx) as *mut u16) = make_vgaentry(c, Black, Yellow); }
- com2kid 13y agoAs others have stated, embedded programming generally avoids malloc. Having all one's memory usage laid out at compile time really does provide some benefits. For one thing, it makes keeping track of who is wasting memory really easy! It is far too common to over allocate a buffer when initially developing code and to not tune it in later. Indeed, having to justify every allocated byte means developers will sit and do math and think about their code before writing it. Odd as it may sound, this takes a fraction of the time that tracing down a memory leak does! Which is where the other huge savings comes in, no more memory leaks! That of course leads right up to the other reason why heap-free programming is so common in embedded: Stability. Memory leaks are a very common class of bug, for deeply embedded devices, it is not reasonable to have the user power cycle. Avoiding memory leaks removes one huge class of bugs. Add to that the lack of threads, and you knock out a second large class of bugs. In the end, one's test surface is greatly reduced! That said, it is an interesting experience, I went from C# to embedded C# (yes it exists! .Net Micro Framework) which generally avoids allocations if possible, to straight embedded C and C++. Some wise guy may now remark about smart pointers, to which I'll reply "my stack is 4k, go away!" Allocating on the stack can still fail with an OOM! Static allocation fails with an OOM at compile time! (Of course it is still possible to blow one's stack, but it is a lot harder when you aren't allocating structs or classes on it!) Oh, and finally, a great interview question is to ask someone where in memory statics are stored. Heck just ask what are the types of memory allocation in C or C++. The percent of candidates that can pass this is quite low! Bonus points if the candidate knows that static consts may be stored in a separate read only region! Super extra bonus points if they list uninit'd and initialized data! That is very much OS and linker options dependent however, assuming one even has an OS! 80%+ of candidates will look at code such as static int16_t value = 5; and, when asked where it is stored at, will answer either heap or stack. (Not quite sure why people say stack.) Really, what you want is to look at a diagram like the one at http://www.geeksforgeeks.org/memory-layout-of-c-program/ http://www.geeksforgeeks.org/memory-layout-of-c-program/ And again, extra credit if they can talk about the various segments on their OS of choice. The above linked most certainly varies by platform, but anyone who has a true understanding of how one platform is laid out will be able to easily comprehend how other platforms go about things. On a more practical note, all this came in handy when using C++ on a platform that didn't call constructors on statically declared classes! I opened up the debugger, looked at my pointer, say a bunch of 0's, then my class data, and realized I had no v-table! (I was crashing whenever I called any virtual functions.) Suffice to say, understanding what a v-table is, and how it worked, and how compilers created them, helped a ton. I then went off to ask the gentleman who wrote our run time why I had no v-table, well, turns out he hadn't written the code to go about and call constructors! It is good to know that all of the "magic" that happens behind the scenes is not magic at all, but perfectly comprehensible code written by a developer just like you or I!