How does memory allocation happen at the lowest level in an operating system?

Question

I'm trying to figure out how memory is allocated at the lowest level in an operating system. From what I can gather is that the operating system is just doing the book keeping of the memory that is available and not available, and it is the C programming language that will do the allocation at the lowest level.

So, the first example is what I came up with as a simple memory allocation system, and then I took an example from the following resource: https://github.com/levex/osdev.

Example-1:

    struct heap_elements {
        int start_address;
        int end_address;
        int size;
        int reservation;
    };

    struct heap_elements heap[25];

    // Write len copies of val into dest.
    void memset(int *dest, int val, int len)
    {
        int *temp = (int *)dest;
        for ( ; len != 0; len--) *temp++ = val;
    }

    /*
    * This function will take a source and destination and copy n amount
    * - of bytes from the source to the destination address. 
    */ 
    void memory_copy(unsigned char *source, unsigned char *destination, int bytes) {
        for (int i = 0; i < bytes; i++) {
            *(destination + i) = *(source + i);
        }
    }

    int find_memory_hole(int size) {

        for (int i = 0; i < total_elements; i++) {
            if (heap[i].reservation == 0) {
                if (heap[i].size >= size || heap[i].size == 0) {
                return i;
                }
            }
        }
        return -1;
    }

    int * malloc(int size) {   
        int hole = find_memory_hole(size);
        if (hole != -1) {
            if (heap[hole].start_address == 0) {
                heap[hole].start_address = ending_address;
                ending_address += size;
                heap[hole].end_address = ending_address;
                heap[hole].size = size;
                heap[hole].reservation = 1;
                kprintf("Starting address: %d\n", heap[hole].start_address);
                kprintf("Ending address: %d\n", heap[hole].end_address);
            } else {
                heap[hole].size = size;
                heap[hole].reservation = 1;
            }
            memset((int*)heap[hole].start_address, 0, size);
            return (int*)heap[hole].start_address;
        } else {
            kprintf("FREE SOME MEMORY~!\n");
            kprintf("WE NEED ROOM IN HERE~!\n");
            return 0;
        }
    }

    void heap_install() {
        total_elements = 25;
        starting_address = 0x100000;  // 1 - MB
        ending_address = 0x100000;    // 1 - MB
        max_memory_address = 0xEEE00000;  // 4 - GB

        for (int i = 0; i < total_elements; i++) {
            heap[i].start_address = 0;
            heap[i].end_address = 0;
            heap[i].size = 0;
            heap[i].reservation = 0;
        }

        return;
    }

    void free(void * pointer) {

        int memory_found = 0;
        kprintf("Address %d\n", &pointer);
        int memory_address = &pointer;

        for (int i = 0; i < total_elements; i++) {
            if (heap[i].start_address == memory_address) {
                heap[i].size = 0;
                heap[i].reservation = 0;
                memory_found = 1;
                break;
            }
        }

        if (memory_found == 0)
            kprintf("Memory could not bee free'd (NOT FOUND).\n");

        return;
    }

Example-2:

    void mm_init(unsigned kernel_end)
    {
        kprintf("The kernel end is: %d\n", kernel_end);
        last_alloc = kernel_end + 0x1000;   // Set our starting point.
        heap_begin = last_alloc;
        heap_end = 0x5B8D80;                // Set the bar to 6 MB
        memset((char *)heap_begin, 0, heap_end - heap_begin);
    }

    void mm_print_out()
    {
        kprintf("Memory used: %d bytes\n", memory_used);
        kprintf("Memory free: %d bytes\n", heap_end - heap_begin - memory_used);
        kprintf("Heap size: %d bytes\n", heap_end - heap_begin);
        kprintf("Heap start: 0x%x\n", heap_begin);
        kprintf("Heap end: 0x%x\n", heap_end);
    }

    void free(void *mem)
    {
        alloc_t *alloc = (mem - sizeof(alloc_t));
        memory_used -= alloc->size + sizeof(alloc_t);
        alloc->status = 0;
    }

    char* malloc(unsigned size)
    {
        if(!size) return 0;

        /* Loop through blocks and find a block sized the same or bigger */
        unsigned char *mem = (unsigned char *)heap_begin;
        while((unsigned)mem < last_alloc)
        {
            alloc_t *a = (alloc_t *)mem;
            /* If the alloc has no size, we have reaced the end of allocation */

            if(!a->size)
                goto nalloc;
            /* If the alloc has a status of 1 (allocated), then add its size
            * and the sizeof alloc_t to the memory and continue looking.
            */
            if(a->status) {
                mem += a->size;
                mem += sizeof(alloc_t);
                mem += 4;
                continue;
            }
            /* If the is not allocated, and its size is bigger or equal to the
            * requested size, then adjust its size, set status and return the location.
            */
            if(a->size >= size)
            {
                /* Set to allocated */
                a->status = 1;
                memset(mem + sizeof(alloc_t), 0, size);
                memory_used += size + sizeof(alloc_t);
                return (char *)(mem + sizeof(alloc_t));
            }
            /* If it isn't allocated, but the size is not good, then
            * add its size and the sizeof alloc_t to the pointer and
            * continue;
            */
            mem += a->size;
            mem += sizeof(alloc_t);
            mem += 4;
        }

        nalloc:;
        if(last_alloc+size+sizeof(alloc_t) >= heap_end)
        {
            panic("From Memory.c", "Something", 0);
        }
        alloc_t *alloc = (alloc_t *)last_alloc;
        alloc->status = 1;
        alloc->size = size;

        last_alloc += size;
        last_alloc += sizeof(alloc_t);
        last_alloc += 4;

        memory_used += size + 4 + sizeof(alloc_t);
        memset((char *)((unsigned)alloc + sizeof(alloc_t)), 0, size);
        return (char *)((unsigned)alloc + sizeof(alloc_t));

    }

From both examples I expected memory that I allocated from malloc() would have the same starting address as to where I allocated it at, if that makes sense? If I know the end of my kernel is at the 0x9000 mark, and I want to start allocating memory at the 1 MB mark. Yes, I know where my kernel is in memory is weird and not conventional, but I know that memory is free past the 1 MB mark.

So, if I know the following:

kernel_end = 0x9000;
heap_starts = 0x100000;
heap_ends = 0x5B8D80;

I would expect that this:

char * ptr = malloc(5)

printf("The memory address for this pointer is at: %d\n", &ptr);

Would be near the 0x100000 memory address but it is not. It is some where completely different and is the reason why I think that I'm not physically telling where the char pointer to be at in memory and that it is the C programming language putting it somewhere differently. I can't figure out what I am doing wrong and it shouldn't be this hard to understand this. Also, I have looked in OSDev Wiki and haven't found anything.

Answer 1

I'm trying to figure out how memory is allocated at the lowest level in an operating system.

Your problem is that you are not looking at how the operating system allocates memory. You are looking at application level memory allocation.

For processes, the operating system only allocates memory in PAGES. A process gains more memory by calling a system service that maps more pages into the process address (ie makes more pages valid).

Because applications usually need memory allocations smaller than a page (for things like strings), heap management functions are often used. malloc and free are rarely (if ever) operating system services.The are simply functions that can allocate memory in increments smaller than a page.

Typically, a call to malloc results in the function trying to find a block of memory large enough to return to the caller. If such a block is not available, malloc will call the operating system service to map pages into the address space to increase the amount of available memory in the heap so that it can return a large enough block of memory.

Answer 2

I'm trying to figure out how memory is allocated at the lowest level in an operating system. From what I can gather is that the operating system is just doing the book keeping of the memory that is available and not available, and it is the C programming language that will do the allocation at the lowest level.

The OS certainly does do bookkeeping for what memory is available and what not, but putting it in those terms vastly oversimplifies, and I suspect you have a different idea of what "memory" means here than best fits.

The OS's virtual memory management subsystem manages how physical memory and other storage resources, such as disk-based swap space, are mapped to each process's virtual address space, including how much and which parts of a process's virtual address space maps to usable memory. It serves requests to increase and decrease a process's available virtual memory, as well as explicit requests to create memory mappings, such as those based on ordinary files.

As far as servicing malloc() calls in a userspace program, you are more or less correct. Programs generally obtain memory from the OS in sizeable blocks, which malloc(), free(), and friends carve up and manage. Typically, those details involve the kernel only when the process fills up the memory already available to it, and needs to request more from the kernel.

But the lowest level is definitely in the kernel. The C library's memory-management functions can work only with memory allocated to the process by the OS.

From both examples I expected memory that I allocated from malloc() would have the same starting address as to where I allocated it at, if that makes sense? If I know the end of my kernel is at the 0x9000 mark, and I want to start allocating memory at the 1 MB mark. Yes, I know where my kernel is in memory is weird and not conventional, but I know that memory is free past the 1 MB mark.

The kernel's view of memory is different from userspace processes'. Each process runs in its own virtual address space, without any visibility into which physical addresses it is using.