2
$\begingroup$

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!

$\endgroup$
7
  • $\begingroup$ Welcome to the Community! You might need to ask this question over at Stackoverflow. Also, you have several questions that should be split into separate questions altogether... [Asking Questions] (cs.stackexchange.com/help/asking) - - also be sure you don't cross-post. Just a friendly heads-up :) $\endgroup$ – phyzyk Mar 7 at 19:04
  • $\begingroup$ Hi there, sure thing - I'll break it up and see what SE says. If I can ask - what's the distinction between CS questions and SO questions? $\endgroup$ – MysteriousWaffle Mar 7 at 19:07
  • $\begingroup$ Here's a link to the help section that should answer all of your questions... Every Stackechange community has one: cs.stackexchange.com/help/on-topic $\endgroup$ – phyzyk Mar 7 at 19:12
  • $\begingroup$ So that there's a link, I've posted part of this in Stack Overflow here which has had some good answers. $\endgroup$ – MysteriousWaffle Mar 7 at 20:04
  • 2
    $\begingroup$ I use this guideline, but please remember that it is just a rough rule of thumb, and is also meant to be taken with a big dose of humor: Stack Overflow is when you are sitting in front of an IDE, Software Engineering is when you are sitting in front of a whiteboard, Computer Science is when you are sitting in front of a blackboard, and Theoretical Computer Science is when you are the one writing on the blackboard. $\endgroup$ – Jörg W Mittag Mar 8 at 10:39
3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ This is fantastic, thank you! Definitely have a good idea of what to look into now :) $\endgroup$ – MysteriousWaffle Mar 9 at 20:10
3
$\begingroup$

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.

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.

$\endgroup$
2
  • $\begingroup$ Thank you very much, pretty much what I was looking for! $\endgroup$ – MysteriousWaffle Mar 9 at 20:11
  • $\begingroup$ Note that, for example in Linux, while there still is a fork system call for backwards compatibility (and there probably always will be for exactly that reason), modern libc implementations are far more likely to implement the fork library function using the clone system call instead. (Glibc does that, for example.) In Linux, the functionality of the clone system call has supplanted the functionalities of all the other "fork-like" system calls such as fork, vfork, etc., not just for processes, but also threads, jails, containers, and even VMs. $\endgroup$ – Jörg W Mittag Mar 28 at 20:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.