Hacker News Reader

Comment by TZubiri | Hacker News Reader

like many C functions you must remember that C is not low level, you won’t learn how memory is allocated by inspecting malloc() anymore than you would learn how characters are printed to the screen by reading printf() or how a file is written by reading write().

you will only learn about the thin or heavy wrapper that C is responsible for, the real magic is happening in the kernel and the device firmware

View on HN

Notwithstanding that most kernels today are written almost entirely in C anyway, you'll see learn a great deal about memory allocation by inspecting malloc().

The usual division of labour in most operating systems is the kernel manages the virtual memory and physical pages and provides a mechanism for coarse page-aligned allocation of virtual address for userland. These coarse mappings userland (malloc or something else) is responsible for carving up, and in that is much design space. Just look at mimalloc for example.

The kernel's own page allocation is often very simple (many get by with a simple freelist, some use buddies.) The allocators for the kernel's own datastructures are usually relatively simple at least conceptually. Bonwick explains the slab allocator - the almost universally acknowledged queen of all kernel memory allocators and mother of those of Linux, BSD, and beyond - in a 12-page paper.

As for the firmware there's basically nothing of an ongoing role for it after the kernel is in charge. Its role is limited for the most part to providing the kernel with a map of the physical addres space.

By reading malloc() you will not learn everything about allocation - that is a problem that spans multiple layers - but you will certainly learn a lot about it. To call it a mere wrapper is not reasonable.

Disagree, I found malloc source useful, and writing a toy allocator especially useful because you learn about the brk() syscall which is a great breadcrumb into kernel land and a great bridge to connect the memory mapping lessons from computer architecture with application code.

Depending on how low-level you're going, you don't even need to call brk.

My toy stop/copy GC and allocation routines just have this:

    %define HEAP_SIZE (4 * 1024 * 1024 * 1024)

    .section bss
    ;;
    ;; Two heaps so we can flip-flop between them
    ;;
    heap_a:
        resb HEAP_SIZE
    heap_a_end:
    heap_b:
        resb HEAP_SIZE
    heap_b_end:

Of course there are other syscalls involved in my compiler/runtime, but for memory allocations the static area sufficed for me.

> and writing a toy allocator especially useful because you learn about the brk() syscall

Nobody in their right mind (except musl) use brk(2) nowadays; mmap(2) is pretty much universally accessible, and brk() has been non-portable for more than 20 years already (POSIX ditched it in 2001) anyhow. For goodness sake, stop keeping this stupid API from VM-lacking PDP-7 alive, and let it go away!

Edit: also, I have no idea how musl even uses it:

    uintptr_t new = ctx.brk + pagesize;
    int need_guard = 0;
    if (!ctx.brk) {
        need_guard = 1;
        ctx.brk = brk(0);
        // some ancient kernels returned _ebss
        // instead of next page as initial brk.
        ctx.brk += -ctx.brk & (pagesize-1);
        new = ctx.brk + 2*pagesize;
    }
    if (brk(new) != new) {
        ctx.brk = -1;
    } else {
        if (need_guard) mmap((void *)ctx.brk, pagesize,
                PROT_NONE, MAP_ANON|MAP_PRIVATE|MAP_FIXED, -1, 0);
        ctx.brk = new;
        ctx.avail_meta_areas = (void *)(new - pagesize);
        ctx.avail_meta_area_count = pagesize>>12;
        need_unprotect = 0;
    }

That's... not what brk() returns; it returns 0 on success and -1 on failure. Huh?

When you call brk() from a user program you use the lib wrapper, and that does indeed return 0 on success and -1 on failure. But the actual Linux system call, which I presume is what musl calls, returns the current break on failure instead of -1.

See the NOTES section in man brk(2):

> C library/kernel differences

> The return value described above for brk() is the behavior provided by the glibc wrapper function for the Linux brk() system call. (On most other implementations, the return value from brk() is the same; this return value was also specified in SUSv2.) However, the actual Linux system call returns the new program break on success. On failure, the system call returns the current break. The glibc wrapper function does some work (i.e., checks whether the new break is less than addr) to provide the 0 and -1 return values described above.

These days brk and sbrk have fallen from grace (and I think even some Unix-likes no longer provide them as general mechanisms, at least I don't think macOS does) - mmap is usually favoured.

Malloc needs the kernel to obtain memory, but in any reasonable implementation (you do not want to make a syscall for every malloc and free) is mostly user space, and studying that will tell you a lot about how your malloc works.

Well, yes, but its low level , no matter what, I mean whats left thats lower?

Reply on news.ycombinator.com