How are kernels (and operating systems in general) written in C?

Question

I'm trying to understand how you set about writing an OS in something like C.

I've always used C to write applications - using commands like malloc and fork and so on to request things from the OS. If these methods don't exist when you're programming the OS itself (or perhaps the Kernel in particular), how do you write them?

If I can summarise what I'm stuck on:

• Am I right in thinking that fork, malloc, etc. are wrapper methods that call the Kernel?

• Do the OS components' code call the Kernel the same way you would call a library? Is it more like it's a microservice you make calls to? When we say that Windows provides a 'hosted' implementation of C, is this what the methods are doing under the hood?

• When you have a 'freestanding' implementation of C, are the standard libraries written in Assembler, but have C headers?

• Are the freestanding components of a hosted C implementation implemented the same way they would be if they were freestanding?

• How do you implement memory and process management in C, what is exposed to allows you to do this in the language? (what do you call to interact with memory / devices / interrupts?)

I can imagine this isn't a small question, so I'm more than happy for an answer that includes some further reading but if you'd be able to summarise the main points related to each question that would be super handy for me!

Thanks in advance!

Answer 1

Today, you can definitely write an OS in C because you have compilers readily available on some OSes. You just have to decide with what executable format you are going to go and then parse it from a bootloader like a UEFI bootloader which has to be written in C as well. Linux is compiled to an ELF executable which is then compressed. Linux follows the multiboot specification (https://www.gnu.org/software/grub/manual/multiboot/multiboot.html) which allows one bootloader (GRUB) to boot the Linux kernel by following the specification.

Am I right in thinking that fork, malloc, etc. are wrapper methods that call the Kernel?

You are quite right. For example, when you write a C app on Linux, you are probably using gcc to compile your app. gcc comes with glibc which is the library implementation of the C standard on Linux. You can look at the source code of glibc (https://github.com/lattera/glibc) to look at the implementation.

For example, malloc is in malloc/malloc.c. Its definition is a one liner like strong_alias (__libc_malloc, malloc) (https://code.woboq.org/userspace/glibc/malloc/malloc.c.html#malloc). I didn't study the source code much but I think this means that a malloc call is a __libc_malloc call. The link I provided is good because it has the function definitions to the right that you can click on to go to the line.

__libc_malloc definition

void *
__libc_malloc (size_t bytes)
{
  mstate ar_ptr;
  void *victim;
  void *(*hook) (size_t, const void *)
    = atomic_forced_read (__malloc_hook);
  if (__builtin_expect (hook != NULL, 0))
    return (*hook)(bytes, RETURN_ADDRESS (0));
#if USE_TCACHE
  /* int_free also calls request2size, be careful to not pad twice.  */
  size_t tbytes;
  checked_request2size (bytes, tbytes);
  size_t tc_idx = csize2tidx (tbytes);
  MAYBE_INIT_TCACHE ();
  DIAG_PUSH_NEEDS_COMMENT;
  if (tc_idx < mp_.tcache_bins
      /*&& tc_idx < TCACHE_MAX_BINS*/ /* to appease gcc */
      && tcache
      && tcache->entries[tc_idx] != NULL)
    {
      return tcache_get (tc_idx);
    }
  DIAG_POP_NEEDS_COMMENT;
#endif
  if (SINGLE_THREAD_P)
    {
      victim = _int_malloc (&main_arena, bytes);
      assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
              &main_arena == arena_for_chunk (mem2chunk (victim)));
      return victim;
    }
  arena_get (ar_ptr, bytes);
  victim = _int_malloc (ar_ptr, bytes);
  /* Retry with another arena only if we were able to find a usable arena
     before.  */
  if (!victim && ar_ptr != NULL)
    {
      LIBC_PROBE (memory_malloc_retry, 1, bytes);
      ar_ptr = arena_get_retry (ar_ptr, bytes);
      victim = _int_malloc (ar_ptr, bytes);
    }
  if (ar_ptr != NULL)
    __libc_lock_unlock (ar_ptr->mutex);
  assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
          ar_ptr == arena_for_chunk (mem2chunk (victim)));
  return victim;
}

__libc_malloc calls _int_malloc which does the main work. It is very long so you can browse it on the link I provided. It is defined as:

/*
   ------------------------------ malloc ------------------------------
 */
static void *
_int_malloc (mstate av, size_t bytes)

I'm pretty sure that this is the malloc you are looking for. In _int_malloc there are these lines:

/* There are no usable arenas.  Fall back to sysmalloc to get a chunk from
     mmap.  */
  if (__glibc_unlikely (av == NULL))
    {
      void *p = sysmalloc (nb, av);
      if (p != NULL)
        alloc_perturb (p, bytes);
      return p;
    }

If there are no usable free chunks in already allocated memory, fallback to mmap to get more memory. sysmalloc is again very long but it calls mmap as a macro defined like:

#define MMAP(addr, size, prot, flags) \
 __mmap((addr), (size), (prot), (flags)|MAP_ANONYMOUS|MAP_PRIVATE, -1, 0)

Do the OS components' code call the Kernel the same way you would call a library? Is it more like it's a microservice you make calls to? When we say that Windows provides a 'hosted' implementation of C, is this what the methods are doing under the hood?

When you write a C app on Linux, you include headers from glibc to use the standard functions like malloc, fork etc. When you compile your app, you either compile it statically or dynamically. When you compile it statically, you include all the kernel code in the executable like mmap's code. Basically, when mmap is called from your main function, the CPU jumps to the function which is mapped in virtual memory. Where it "stops" including the code, is when you jump to kernel code using int 0x80 on older x86 32 bits processors. I don't know about the system call convention for x86-64 honestly. It is probably similar. When your code calls int 0x80 on x86, it interrupts the CPU and it jumps to shared-by-all-processes kernel code. This kernel code cannot be included in your executable because it is interrupt code. So mmap is included in your executable up until the system call. The rest of the work is done in the interrupt handler and then returns to mmap which now has the new address of the allocated memory chunk. mmap then returns to the glibc caller which, like you said, is a wrapper around kernel code calls. When you link dynamically, it is the same except linking happens just before runtime.

When you have a 'freestanding' implementation of C, are the standard libraries written in Assembler, but have C headers?

You don't need to write the implementation of C in assembly. glibc is written completely in C. Most of the Linux kernel is also written in C. Some parts of the kernel code needs to be written in inline assembly. For example, the system calls need to be done with a int 0x80 call that you can't make from pure C.

Are the freestanding components of a hosted C implementation implemented the same way they would be if they were freestanding?

This is a lot of terminology and I don't get what you mean by freestanding and hosted here. A freestanding implementation means that you use only the base of C because you don't have access to library functions like you would in a development environment like Windows or Linux. For example, an OS needs to be written in static, freestanding C because you need all code to be included in the final executable and because you can't depend on a runtime which includes things like standard libraries, system calls and other stuff like that. Actually, freestanding means that you really use only the components of C that you know are going to be included in the final executable and which are going to be compiled to assembly which doesn't depend on a particular runtime.

How do you implement memory and process management in C, what is exposed to allows you to do this in the language? (what do you call to interact with memory / devices / interrupts?)

C includes pointers which allow to do all that and more. In a freestanding environment (like when you develop an OS), you can just use absolute addresses and it just works because you don't have things like memory protection. You do have memory protection but you are the one in control of it. If you just type something like int* pointer = (int*) 0x8000;, you have a pointer of type int which points to 0x8000. If you type *pointer = 0x34, then at the address 0x8000 is now 0x00000034. That is because an int is 4 bytes. If you type unsigned char* pointer = (unsigned char*) 0x8000, and then *pointer = 0x34, at the address 0x8000 is now 0x34. That is because a char is one byte. You see that you can control memory pretty easily in C. You can put whatever values you want at the byte level. You can even work at the bit level using bitwise operators.

Today, most devices have memory mapped registers. By accessing memory using pointers, you can write commands to the registers of these devices and tell them to do stuff. If you ever need to access some IO ports or to do a system call like with int 0x80 then you have inline assembly from C which allows to do it. Also, the BIOS builds ACPI tables in RAM in conventional position which allows the OS kernel to find the location of the different registers.

Hope this answers your questions.

Answer 2

There's a lot to unpack here, but I'll try to keep it as Computer Science as I can.

Am I right in thinking that fork, malloc, etc. are wrapper methods that call the Kernel?

Yes and no, respectively.

In a typical POSIX-like operating system, fork is a system call. This means that there is usually a very thin wrapper, often written in assembly language, which has three jobs:

• Translate between the C calling convention and the system call convention. This usually means transferring arguments between registers.
• Invoke the system call.
• Do any processing needed for the return value from the system call. Again, this is usually just a register transfer today.

Note that Windows does not support fork.

This is not true of malloc. Modern operating systems manage program memory in terms of pages; a program can only allocate or deallocate a whole number of pages. If finer-grained allocation is needed, then the user program needs to implement a data structure on top of this.

This is also how different programming languages can use different allocation models, such as garbage collection. Programming languages don't need to follow the same heap model as malloc(). Windows has support for logically separate heaps through heapapi.

Remember that disks and SSD storage don't have a concept of "files"; a disk is just presented as a big array of blocks (to a first approximation). Similarly, operating systems don't have a concept of "heap allocated objects"; address space is just a big array of pages.

How do you implement memory and process management in C, what is exposed to allows you to do this in the language? (what do you call to interact with memory / devices / interrupts?)

What a programmer thinks of as "allocating memory", to an operating system, really means allocating virtual memory, so this is understood as a virtual memory operation. Specifically, "allocated memory" is known as "anonymous memory", which distinguishes it, say, memory-mapping a file (which, therefore, has a "name" and is not "anonymous").

Different operating systems provide different ways to achieve the same result.

• In traditional Unix-like operating systems, heap memory used to be allocated with brk and sbrk. Today, it is more usually achieved by memory-mapping a special device called /dev/zero, which the kernel understands to mean "anonymous memory".
• In Mach (and hence MacOS), there is a system call called vm_allocate.
• Windows has a very similar system call to Mach, called VirtualAlloc.

Do the OS components' code call the Kernel the same way you would call a library? Is it more like it's a microservice you make calls to? When we say that Windows provides a 'hosted' implementation of C, is this what the methods are doing under the hood?

The "typical POSIX-like operating system" that I mentioned above is how things work in Linux, MacOS, and so on. The C standard library for that platform provides system calls as if they were normal C functions.

Windows is a bit different. System calls are invoked through a system DLL called kernel32.dll. (Yes, even on 64-bit platforms!) In Linux, you need to call system calls to load dynamic shared objects (DSO being the generic term for what Windows calls a DLL), which would cause a bootstrapping problem if you needed to load a DSO to invoke a system call. In Windows, DLL loading is partly managed by the kernel, so kernel32.dll can be supplied to user programs without needing any system calls to set it up.

When you have a 'freestanding' implementation of C, are the standard libraries written in Assembler, but have C headers?

Are the freestanding components of a hosted C implementation implemented the same way they would be if they were freestanding?

"Freestanding" means two things:

1. The entry point to the program need not be main().
2. The C standard library need not be present.

That last one is probably the most important. You see, C compilers are allowed to assume that the C standard library is present, and generate calls to it even if there isn't an explicit function call. One common example is that copying large structures can be implemented with a call to memcpy(), as you can see for yourself.