#FrostyOS

1 messages ยท Page 4 of 1

celest sierra
#

pointing to random memory

dusky orbit
#

lol - yeah it would ๐Ÿ˜…

#

clearly didnt think that one through before sending it

lost schooner
#

Yes

dusky orbit
#

ah I was thinking of the global bit

lost schooner
#

What makes this more annoying is that the custom page table hasn't even been loaded yet

lost schooner
#

i can confirm the issue is unrelated to the PAT

lost schooner
#

this scrolling is so slow

#

i'm tempted to hack in some double buffering to speed it up

lost schooner
#

i decided to do it

#

due to lack of a vmm, I'm just putting a 16MiB raw buffer inside the kernel image

#

this is just temporary so I can debug easier on real hardware

#

first attempt resulted in an empty screen

#

second (latest) one resulted in a triple fault

#

and its working

#

it was such a stupid mistake

#

scrolling is so fast on real hardware now

#

like at least 100x QEMU

#

but, I can confirm my 1GiB page mapping function is not the issue

#

there is something else someone hiding from me

lost schooner
#

somewhere not someone

brittle crow
lost schooner
lost schooner
#

it seems to work no issues if I don't check if 1GiB pages are supported

#

it is only when I do check that things go badly

#

yep, I can confirm that the page tables are perfectly valid for the 6 or 7 1GiB pages

#

so more asm function for checking has some issues some how

#

hopefully its something stupid like forgetting to pop something or forgetting to save a register

#

well I found something wrong

#

but it is for the case where 1GiB pages aren't supported

#

when I know they are

#

now it works???

#

I'm going to boot to arch on it and just see what it says about 1GiB pages

#

linux claims that 5 1GiB pages are being direct mapped

#

maybe I'm doing the wrong cpuid

#

I found the mistake

#

so stupid

#

I was anding the correct bit, but testing the wrong register

#

and it all works

#

finally

#

I can't believe it took me that long to find the problem

#

I'll do some clean-up, commit this and merge to master

#

then it'll be IRQ time

#

I'm going to keep the double buffering support, because I'm sure it will be useful later

#

but I will get rid of the cursed 16MiB raw byte buffer in the kernel

#

I'm going to stick with the do while based assert as it just seems better

#

and also works for both C and C++

#

and it is merged

#

I'm starting to wonder whether or not I should do the IRQ system now

#

I want to have full APIC support, but that requires the ACPI tables

#

and if I want to use uACPI for that and not just some temporary crappy tables, I need a VMM and heap

#

so maybe I should just start the VMM

#

the whole reason I wanted to make the IRQ system and scheduler first was so the scheduler doesn't use the heap or VMM

#

another bonus of doing the scheduler first is that I'm forced to make the VMM thread safe

#

I'm going to think about all this for a bit

dusky orbit
dusky orbit
lost schooner
#

Yeah, I might just do that

#

I can always replace it with uACPI in the future

dusky orbit
#

also you dont need to include 40kloc for parsing some simple structs that way too meme

lost schooner
#

yeah

lost schooner
#

since I'm lazy, I'm just asserting that the XSDT exists

#

and not bothering with RSDT

dusky orbit
#

its only a handful of extra lines to support the rsdt, well worth it imo

lost schooner
#

I can't be bothered to. This code won't last long anyway

#

so far things are going well:

image.png
#

I'm going to make some changes due to ACPI only guaranteeing 4 byte pointer alignment

#

that took way longer than it should have, but I think it works

#

and UBSan doesn't complain

#

unlike my previous kernel

lost schooner
#

had to have a short break, but now I have MADT parsing working:

image.png
#

that last entry looks a bit odd, so I'll look into that

#

that's better:

image.png
#

now I think I'll quickly get the legacy i8259 PICs handled

lost schooner
#

well that works

#

unfortunately I've ran out of time for today

lost schooner
#

doesn't look like much, but has taken a decent amount of effort to get to this point:

image.png
lost schooner
#

I'm going to attempt to do what the SDM says and map the LAPIC registers as UC

#

it's going to be annoying though due to the HHDM

hollow trail
#

Why

#

You have MTRRs

lost schooner
#

so if the MTRRs are set properly, I don't need to bother?

#

I forgot about this:

image.png
#

as long as the MTRR is set as UC, then regardless of what the PAT says, it should be UC

#

other than WC, which I only map the framebuffer as

#

so what I was about to do was going to be a waste of time

hollow trail
#

Which they are

lost schooner
#

what about on the APs?

#

will it be consistent?

hollow trail
#

They should really copy the BSP settings

lost schooner
#

ok

hollow trail
#

Or you will have very interesting corruptions

lost schooner
#

so I shouldn't realistically need to touch the MTRRs at all?

hollow trail
#

Yes

lost schooner
#

ok

lost schooner
#

I'm not sure whether or not I want to do SMP start-up now, or wait until I have a VMM

#

If I do it without a VMM, I'm not going to be able to get a proper stack on the APs

#

so it might have to wait

#

I don't think I can do the IRQ system properly without a heap

#

it will just be a mess

#

so I don't think it is worth it

#

I think I'm just going to clean-up the current LAPIC, basic ACPI tables, and 8259 PIC code and commit it.

#

then tomorrow I'll start on the VMM

#

I forgot about the scheduler

#

I could attempt it

#

but I won't be able to make it preemptive without a timer

#

Even if I use the LAPIC timer, I need something to calibrate it with, which means an IRQ system

#

so once again, I think it is a better choice to just move on to the VMM

hollow trail
#

Ill add heapless uacpi table support soon and maybe even an option like UACPI_TABLES_ONLY

#

So that even most basic kernels can start with uacpi before they have anything available

#

And then enable proper uacpi later on

lost schooner
#

that would be quite useful

hollow trail
#

Instead of refactoring table find code later to use uacpi which is annoying

hollow trail
lost schooner
#

for some reason my spinlock.h was missing a copyright header

#

I wonder if that is a remnant from the old kernel

#

I'll read the working set paper a bit more, so I understand it enough to make an implementation

hardy lake
#

https://en.wikipedia.org/wiki/Page_replacement_algorithm

Page replacement algorithm

In a computer operating system that uses paging for virtual memory management, page replacement algorithms decide which memory pages to page out, sometimes called swap out, or write to disk, when a page of memory needs to be allocated. Page replacement happens when a requested page is not in memory (page fault) and a free page cannot be used to ...

#

read this too

lost schooner
#

thanks, I'll read that as well

lost schooner
#

I think I might need to make a virtual region allocator first, but I'm not sure

#

No I don't

#

But I do need a VMM heap

#

So I think I will just do what I did with my last kernel and have a separate VMM heap which uses PMM pages

lost schooner
#

I think I want to make it a slab allocator, but I'm not sure how many sizes I'll need

#

Maybe I'll start with 16, 32, 64, and 128

lost schooner
#

time to stop procrastinating and just get this done

lost schooner
#

Heap allocation should be O(1), but unsized free is looking like it could be O(n^2)

#

sized free is O(n)

#

Actually, I have a stupid but functional idea for making any free O(n)

lost schooner
#

I couldn't work on this at all yesterday because I decided to go outside for the first time in a while. I have a lot of time today though

hardy lake
#

outside? what's that?

lost schooner
#

hopefully I have finished implementing the vmm heap

#

time for testing

#

not a good start:

image.png
#

I'm very tempted to use the heap from my old kernel

#

because it worked

#

what I have just tried to make was a disaster

#

I won't use the heap from my old kernel, but I am going to attempt to make one that follows the same concept

#

just hopefully faster

#

because I'm going to try make it in a way where the whole heap doesn't need to be locked on every operation on it

lost schooner
#

I have successfully implemented allocate of a hopefully better heap

#

it can get to 57/100000 iterations of my test before it freezes

#

so stupid

#

I fixed a bug, now it gets to 11 before it page faults

#

which is worse in some ways

#

another bug fixed and it is back to 57

#

I found the bug

#

100 thousand iterations of the test were successful

#

just need to add merging of free blocks

#

and removal of empty chunks

#

wait

#

I just realised my free isn't doing anything

#

making free actually work, including merging of free blocks results in it freezing at iteration 123

#

I just realised why though

#

I'm dealing with the typical remove 1 bug, and 3 appear in its place

lost schooner
#

finally it works

#

after so many bugs

#

I forgot something, and now it is back to failing

#

this time something is nullptr when it shouldn't be on iteration 51

#

1 bug fixed, another appears in its place

lost schooner
#

I decided to add a Verify() function like in my old kernel

#

and it gets to iteration 368 before it fails

#

after improving Verify() even more, it only gets to iteration 7

#

which is not good

hollow trail
#

What iteration

lost schooner
#

of the test I run

hollow trail
#

Oh

lost schooner
hollow trail
#

Yeah oberrow needed this test

lost schooner
#

it's just a single threaded test, but later I'll make a multi-threaded one once I have SMP and a scheduler

hardy lake
lost schooner
#

time for more debugging

#

just found and fixed one bug

lost schooner
#

allocate is fixed finally

lost schooner
#

free is being a pain

#

finally it works

#

time for auto shrinking

#

which I hope works

#

this is definitely wrong:

image.png
#

i see the problem

#

so stupid

#

that is better:

image.png
#

after realising a had forgotten a simple continue;, it now works fully

#

just need to add proper reporting of the current heap memory usage areas

#

that will be free mem, metadata mem, used mem, and total mem

#

then after that, VMM heap is done for now

#

I'll have to do further testing later once I have SMP

lost schooner
#

for realloc, I'm just going to take the lazy option and instead of checking if the block can expand, I'll just allocate a new one

#

1 million iterations of the test are successful, so I think I can say that the VMM heap is done

lost schooner
#

I guess now I have to start making a working set implementation

lost schooner
#

The problem is, I have no idea where to start

lost schooner
#

I'm starting to wonder if I need a scheduler first

lost schooner
#

ok, I'm starting to understand more

#

I think I need to have the concept of processes, but not necessarily a scheduler

#

I understand that the working set is essentially just a list of pages being used by a process

#

I assume a linked list will do for that

lost schooner
#

I don't understand the size/capacity stuff

#

I think I understand now

#

I know I need to set a minimum and maximum size

#

but how to calculate that, I don't know

#

I understand what they are, but not how to calculate them

hardy lake
#

A list of pages in a process that need to be swapped in for the process to run as efficiently as possible

#

My size field is simply the size of all pages in there

#

The capacity is the maximum size of the working set

#

Size must be <= capacity

#

The capacity should be constant

lost schooner
hardy lake
#

No a list of pages used by the process is different

#

You would use one of the page replacement algorithms I sent to determine what pages go in the working-set

lost schooner
#

Oh

#

I'll have another look at it tomorrow

hardy lake
#

Ok

lost schooner
#

If I try look at it now, I might read it, but won't absorb any information from it

hardy lake
lost schooner
hardy lake
#

Just clearing any possible confusion

lost schooner
#

alright, time to look at page replacement algorithms again

lost schooner
#

so far, Not recently used (NRU) is looking good, but Least recently used (LRU) might be better

#

actually LRU is much better

#

an interesting method is:

Another method that requires hardware support is as follows: suppose the hardware has a 64-bit counter that is incremented at every instruction. Whenever a page is accessed, it acquires the value equal to the counter at the time of page access. Whenever a page needs to be replaced, the operating system selects the page with the lowest counter and swaps it out.

#

i don't think that is possible on x86_64 though

#

there might be other archs that can do it, but I have no clue

full needle
#

you probably don't need a counter that's per every insn?

#

i'd imagine any monotonic counter works, so on x86_64 the tsc

lost schooner
#

yeah, I guess every timer tick I can use the tsc value as the timestamp

#

after thinking a bit, I'm going to change the order I'm going to do things in

#

I'll put aside the working-set, page cache, and page replacement stuff for now

#

Then I'll follow this order:

  1. Virtual Memory Allocation
  2. kernel heap (same as VMM heap except will use pages from the VMA)
  3. IRQ system + SMP startup
  4. preemptive scheduler
  5. working-set, page cache, and page replacement stuff
#

the reasoning behind this is that a need a IRQ system to properly make a page cache

#

so I thought while I was at it, I might as well do SMP startup and start on the scheduler

#

as for the reasoning being the VMA and kernel heap, I want to use the heap to allocate objects for the IRQ system and thread/process states

#

now I need to think about how to approach virtual memory allocation

#

My old kernel did some weirdness with AVL trees and linked lists, but I don't know how well that actually performed

#

free list search was O(nlog2(n))

#

reserved/used list search was O(log2(n))

#

so it was all in logarithmic time

lost schooner
#

searching for a node in the tree was O(log2(n), and then searching for a node in the list within the tree node was O(n)

#

I'm not sure if I want to try do something similar in this kernel

#

now I think even more about the old kernel, the finding of a node of an appropriate size in the free pages tree, was horrible

#

first it would search the entire tree for a node of matching size, then it would like for one that is bigger

#

I could just use a linked list

#

but with how frequently virtual memory allocation occurs, that might be too slow

#

AVL trees have more memory overhead per node, but are so much faster

#

I think I'm going to try do something with AVL trees again

lost schooner
#

I could try use a RB tree, but I already have an AVL tree implementation

#

I might actually use the same data structures as my old kernel

#

because sorting free pages by size is more optimal as allocation is normally requesting pages based on size

#

it is rare for address-based allocation requests to occur

lost schooner
lost schooner
#

and to defragment efficiently, the tree needs to be temporarily reformed into a tree sorted by address

#

so maybe I need to think of other options

#

I can think of a way to deal with this, but it will have double the memory overhead

#

actually, it's not quite double

#

since I'm bored, I'll describe my idea

#

I could potentially have 2 trees, one sorted by size, other by address

#

the one by address doesn't need the linked list at each node

#

so it has an overhead of 40 bytes per region

#

the one by size has an overhead of 40 bytes by size, then 24 bytes for each address within those sizes

#

but, I just thought that I could merge the user/reserved tree with the free tree sorted by address

#

so no extra overhead

#

from the original idea

#

maybe that might work

#

there still is the problem of the free pages tree needing to be rebuilt frequently

#

there definitely must be a better solution

hardy lake
hardy lake
lost schooner
lost schooner
hardy lake
hallow bluff
hardy lake
#

wait I took mine from openbsd

#

as in, my tree.h

hardy lake
#

if it helps

hallow bluff
#

there isn't a great deal of difference in terms of performance characteristics

lost schooner
#

I'll look into it more when I have time. Tomorrow, I probably won't have much time

lost schooner
#

I got some time now

lost schooner
#

AllocatePages is done

#

and FreePages is done with no merging of free regions

#

I just want to test the basics first

#

before I attempt the mess it will be

#

also need to do reserve/unreserve later

lost schooner
#

had to disappear last night before I could run the test, so I'll do it now

#

I'm using my kernel heap test, just slightly modified

#

and it fails during iteration 3

#

with a page fault

#

I'm just going to get GDB ready

#

because I know I'll need it while debugging this at some point soon

lost schooner
#

after a couple of very stupid bugs, it gets to iteration 2468

#

it fails in the heap

#

oh no

#

this can't be good

lost schooner
#

I'm currently avoiding this project as I don't feel like dealing with the heap

#

When I feel like dealing with it, I think I'll modify my heap test a bit and rerun it

celest sierra
#

just fix your heap instead of fixing the test lmao

#

does the test even work when you run it under linux (with glibc)?

lost schooner
lost schooner
#

I forgot to actual check the heap object could be read to / written from freely after being allocated

celest sierra
lost schooner
#

it would make debugging easier

lost schooner
#

time to stop procrastinating and get back to this

#

looks like my suspicions about the VMM heap are true

#

it is dodgy

#

I deliberately added a line in my VMM heap test to fill each allocated buffer with 0x41

#

and I get a GPF

#

RemoveEmptyChunk chunks is responsible

#

wow I'm really struggling to type properly at the moment

#

why is there a separate function in the objdump called Heap::RemoveEmptyChunks.cold?

#

which a bunch of ud2s

#

and mov rax, QWORD PTR ds:0x0

#

weird

#

and it makes a magic call to something r12 points to?

#

not related to the problem though

#

something weird is definitely going on:

image.png
#

those sizes are very high

#

I'm going to test this in a userspace program

#

getting a userspace program was just annoying

#

not hard at all

#

just dumping lots of stuff into one source file

dusky orbit
lost schooner
#

that code appears to be unreachable, but still weird that it isn't a bunch of nops

lost schooner
#

i once again spent another whole day procrastinating to avoid dealing with this

#

turns out the wrong sizes bug was due to me memseting the buffer at the wrong time

lost schooner
#

I've been trying to debug something for the last couple of minutes that is entirely my fault

#

as in, bad porting to a userspace program

#

I was using malloc/free when I should be using mmap/munmap to have similar conditions to kernel space

#

metadata seems to be getting overridden under certain conditions:

image.png
dusky orbit
#

damn sounds like a heap (ha) of memory management issues ๐Ÿ˜ฆ

dusky orbit
lost schooner
#

No

#

Not at this stage

#

Just dumped the vmm heap code plus the bitmap code into a file along with a main function to run the test

#

Along with some headers that are exclusive to my kernel

lost schooner
dusky orbit
#

lol

dusky orbit
lost schooner
dusky orbit
#

could it be an overrun/underrun somewhere?

lost schooner
#

I don't think so:

image.png
#

I can confirm that the current issue is unrelated to removal of empty chunks

dusky orbit
#

have you tried logging everything at every step in alloc/free and seeing if all the details match?

#

maybe some bad pointer maths or alignment happening somewhere

lost schooner
#

it must be happening under a very specific condition because the test gets to 2207 iterations

#

I'll try adding even more logging

#

so my Verify() is reporting an invalid size at entry to Heap::alocate on iteration 2208

#

if I read that block as a void*[2], I get 16 bytes of 0x41

#

which tells me that the metadata for that block is being overridden somehow

dusky orbit
#

what I've done in the past is put some checksum in each block of metadata and very it with each alloc/free call

#

maybe thats useful to you

lost schooner
#

I found out what is happening

dusky orbit
#

oh?

lost schooner
#

the previous allocation is at 0x...3dc0

#

of 576 bytes

#

which means it ends at 0x...4000

#

but the block's header with the overridden metadata starts at 0x...3ff0

#

so I'm suspicious that the size of a block was wrong

dusky orbit
#

hmm progress

lost schooner
#

I think I might have tracked down a condition for this to occur

#

still need to investigate further

#

its very similar to what I saw before, except no metadata corruption yet

#

I was correct

#

it works

#

time to re-enable removal of empty blocks

#

still works

#

alright, time to get this back into the kernel

dusky orbit
#

nice

lost schooner
#

The issue was quite simple once I realised what was happening

#

I was forgetting to subtract the size of the metadata under 1 specific condition

dusky orbit
#

haha ah its always something simple

lost schooner
#

also works in the kernel

#

finally I can get back to my virtual memory allocator testing

#

my vma test passes

#

how

lost schooner
hardy lake
lost schooner
#

I hope not

hardy lake
#

you have been trying to fix heap bugs for the past 3 weeks maybe

lost schooner
#

procrastination

#

not as bad as my 4 or 5 months at the end of 2022, beginning of 2023

#

its been 11 days not 3 weeks

#

first started on the VMM heap on the 17th

#

its now the 28th

#

after procrastination and distractions, free region merging should be done

#

the code is a bit weird to restrict the amount of locking

#

which I just realised whilst sending this is a waste of time

#

sort of anyway

#

it needs to be locked the whole time

#

wait no

#

I'm overthinking it

#

no now I am

#

ahhhh

#

This looks very much initialised to me:

image.png
#

anyway

#

I get a page fault

#

due to a nullptr dereference

#

my new code is stuffing up the free tree

#

I found a bug

#

slight improvement

#

now I get an assert to deal with

#

looks like there is mismatched data between the 2 trees

#

I'm going to deal with this tomorrow

lost schooner
#

I have tried formatting it in multiple ways, but it still says it is uninialised, when it isn't

celest sierra
#

can you show the full code?

lost schooner
celest sierra
#

uhhhhh

#

stinky

#

why are you dereferencing data as uint64_t?

lost schooner
#

because the insert function takes a uint64_t

celest sierra
#

right, i think this is ub though

#

aliasing and all that fancy stuff

#

idk if that stuff matters right now tho

lost schooner
#

if I just do *(uint64_t*)&data, I get a strict aliasing warning

celest sierra
#

yeah...

lost schooner
#

so I was trying to avoid that

celest sierra
#

you shouldn't do that

#

you are still doing that though lmao

#

use a union instead

#

or maybe you can do some std::bit_cast stuff

#

or std::launder, idk how all that modern c++ stuff works

#

but i know you can do some aliasing with that somehow

lost schooner
celest sierra
# 
union {
  PageRegionData data;
  uint64_t uint64_value;
} u = {.data = {...}};
map.insert(..., u.uint64_value);```
#

or something like that

#

or std::bit_cast

#

assuming sizeof(PageRegionData)==sizeof(uint64_t)

lost schooner
celest sierra
#

i think you might be able to use std::bit_cast then

lost schooner
#

is that freestanding?

celest sierra
#

it's defined in <bit>

#

should be..?

#

available since c++20

lost schooner
celest sierra
#

unless your license prohibits you from doing that

#

it really just boils down to a compiler builtin

lost schooner
#

github is having a moment:

image.png
celest sierra
#

lmfao what the heck

lost schooner
#

that repo has GPLv2 and GPLv3

celest sierra
#

i think so, yes!

#

but im not the license guy so

#

ยฏ_(ใƒ„)_/ยฏ

celest sierra
#
  1. The Free Software Foundation may publish revised and/or new versions
    of the General Public License from time to time. Such new versions will
    be similar in spirit to the present version, but may differ in detail to
    address new problems or concerns.

Each version is given a distinguishing version number. If the Program
specifies a version number of this License which applies to it and "any
later version", you have the option of following the terms and conditions
either of that version or of any later version published by the Free
Software Foundation. If the Program does not specify a version number of
this License, you may choose any version ever published by the Free Software
Foundation.
that would imply that you can use this code with any project that uses gpl >=2

lost schooner
#

ok

#

I decided just to use a union for now, but will probably use those headers at some point in the future

lost schooner
#

I have now fixed the mismatched size problem, now I am dealing with something that isn't free being in the free tree

#

to debug this easier, I'm trying to get lambda captures to work

#

I want to try do it without std::function, but have no clue how

lost schooner
#

I gave up and just decided to use a void* for extra data

lost schooner
#

that region shouldn't even be in the free tree

#

by randomly commenting out stuff until it works, I have determined that this code is responsible:

image.png
lost schooner
#

might not be directly

#

could be indirectly

#

it might just allow it to be detected

#

my suspicion that there might be duplicate addresses in the tree was wrong

#

next I will check for overlapping entries

#

and I was correct

#

there is an overlap

#

all this verify stuff is just to test the allocator

#

once it works, I will remove the Verify()s

#

because they are very slow and heavy on the VMM heap

#

the VMM heap heavy stuff is to speed it up a little

dusky orbit
#

you're only supposed to access the last member assigned to (because of lifetime stuff) so in that case that would only be allowed if you wrote to uint64_value and not data anyway.

sand scaffold
#

so what?

dusky orbit
#

I thought C allowed it?

dusky orbit
#

so what? so dont do it lol

#

or do, and deal with the behaviour you get

hollow trail
#

union type punning is not ub in c

hollow trail
sand scaffold
#

union { float a; int b; } c; c.a = 1.0f;

#

is c.b supposed to always be 0x3f800000?

hollow trail
#

whatever the representation of 1.0f

#

yes

#

thats one of the reasons why c++ sucks for osdev

dusky orbit
#

yeah it is annoying

#

nothing a little memcpy cant fix though meme

sand scaffold
#

that's kinda stupid

dusky orbit
#

its really stupid

#

unions in c++ really got left behind

#

there's all kinds of edge cases with them

celest sierra
#

ah my bad

#

so bit cast is the way then?

#

or memcpy lol

hollow trail
#

Yeah

sand scaffold
#

makes total sense !

celest sierra
#

__builtin_bit_cast my beloved

hollow trail
#

do u know how it works?

# 
T val;
memcpy(&val, src, sizeof(val));
return val;
sand scaffold
hollow trail
#

because it makes the modifications via the type punned value escape the compilers ability to recognize modifications

#

and prevents a lot of optimizations

#

and its an uncommon thing so its good to optimize it

tired cedar
tired cedar
#

sounds like a violation of strict aliasing to me

hollow trail
hollow trail
tired cedar
#

honestly this is rather cursed

#

it means that #define foo(x) (*&(x)) is not equivalent to #define foo(x) (x)

#

i think?

hollow trail
#

Probably because no constructors or object lifetimes as strict as c++

hollow trail
tired cedar
#

oh wait maybe it is

hollow trail
tired cedar
#

what the fuck is this

hollow trail
#

This explains it more I think

celest sierra
#

"I don't have my copy of C90 at hand to verify the context"

#

holy FUCK

sand scaffold
#

So whats the point of unions if their main purpose is U.B.

celest sierra
#

in C++ type punning using unions is UB

#

in C it's the way you do type punning

hollow trail
#

e.g. tagged unions

sand scaffold
#

reinterpret cast?

celest sierra
#

std::bit_cast

#

or some sort of reinterpret_cast, but idk

#

bit_cast works well for simple types like float/int/double

#

but i don't think you'd want to do that on a big ass struct for example

#

i'm not a C++ person tbh so i don't have the answers

hollow trail
hallow bluff
lost schooner
#

I'm back at school now, so I don't have as much time

lost schooner
#

after looking into this overlap further, I have discovered that the smaller region is the end of larger one

#

both of which seem to have a valid reason to exist, but not quite sure

#

I'm going to check for overlaps in the all address tree as well

#

to attempt to find the source of the issue

#

I caught something a lot earlier in the all address tree

#

this math doesn't add up

#

supposedly the bad region has a size of 570 pages when it should be 480

#

which would mean no overlap

#

wait

#

there is a use after free here

#

there we go

#

seems to be running well now

#

taking ages because of the checks

#

running at ~100 iterations per second

#

its down to 20/s now

#

too slow

#

I'll disable the overlap checking

#

and it works

#

with kvm back on, all 100k iterations, no overlap checking takes less than a second

#

1M takes a few seconds

#

10M took about 45-60 seconds

#

with no verify, it only takes 10-15 seconds

#

not a good way of benchmarking, but can be used a guide that it is fairly fast, but does slow down when it has a lot more regions to deal with

#

not directly related, but I just built my kernel with -O3 instead of -O2 for the first time and it works perfectly fine

#

not a noticible performance impact

#

I leave it at -O2 to make debugging a little easier

#

not really important, but all this new stuff does work on real hardware

#

with and without ubsan

#

Need to improve the allocator a bit, such as address-based allocation

#

which will hopefully include the ability to reserve regions

#

then I should be able to move on to some kind of PageManager or PageAllocator

#

need to think about the naming a bit

#

the virtual memory region allocator is currently called the VirtualMemoryAllocator

lost schooner
#

allocating at a specific address is now supported

#

need to do some testing, but hopefully it works

lost schooner
#

and it doesn't...

#

overlap on the first allocation

#

stupid mistake

#

I was subtracting and address from another forgetting that I need to divide by PAGE_SIZE after

#

gets to iteration 271 now

#

I forgot to mention that it is pretty much the same test as before, except some slight modifications so that a random address which isn't already in use is selected

lost schooner
#

after some minor bugs, it seems to work

#

I've got the test running 100k iterations, full verify with overlap checking

#

so it might take a while

#

oh and I just realised ubsan is on

#

its been running 5 or so minutes and is at 56k, so I'll leave it to finish

#

even though it is only single threaded, my CPU is slowly warming up my room

lost schooner
#

so it slows down with the more regions to work with

lost schooner
#

its almost done

#

99k

#

only ~1k left

#

it finished

#

I forgot the finish message goes to the screen not the debug console, so I didn't realise until I heard the CPU fan suddenly go a lot quieter

#

the height of the freeSizeTree is 9

#

and 10 for the all address tree

#

I just quickly ran it again with no verify, and freed all the allocated blocks at the end, and the height of both trees is 1

#

I starting to wonder if frees were dodgy after seeing thoses sizes, but this test confirms merges are working perfectly well

#

due to this test taking ages, I'm out of time today

#

tomorrow I'll do reserving, and proper tracking of free/used/reserved page counts

#

then the allocator should be done

dusky orbit
#

cool, thats some serious testing

lost schooner
#

yeah, I don't want to have the same issues as my last kernel where many things were going wrong at once, and it was a massive pain to debug

#

and this time I'm trying to make everything with multithreading support in mind

dusky orbit
#

yeah I respect it, might be the most thorough testing in this server besides uacpi

lost schooner
#

I'm interested to see how uacpi will go running in this kernel once I'm ready to add support for it

#

If I really wanted to, I could implement it after the kernel heap, and replace my temporary ACPI table parsing

#

but there isn't much point

dusky orbit
#

fair enough

muted blade
#

uStressTest

hollow trail
lost schooner
#

That isn't my problem with doing it earlier, but good to know

lost schooner
#

reserve/unreserve should be done

#

reserve is very similar to allocating at a specific address and unreserve is essentially free

#

I'm going to run a similar test as before. I'll take out the overlap detection because I really don't feel like waiting another 35 minutes for a simple test

#

and it works

#

nice

#

time for proper tracking of reserved/free/used page counts

#

wait, that was already happening

#

it isn't happening properly

#

The code it there, but at the end when I check everything, the counts are wrong

#

found the bug

#

the pageCount argument gets updated in certain situations, but it was still being used at the end to update the counts

#

so instead, I have an initialPageCount, that is set at entry to the functions, which is const so it can't be modified

#

and the VirtualMemoryAllocator is done

#

I'll do some clean-up, get this properly setup, and commit it

#

clean-up is done, there is some documentation on how it operates for allocation and freeing, but not how reserve/unreserve works

#

Now I need to set it up properly

#

I think I'm going to have a global instance, which covers all of address space

#

and then a kernel allocator for the last 2GiB of address space for now

#

later, each userspace process will have its own instance ranging from the beginning of the 2nd page (0x1000) to the beginning of non-canoncial address space (1<<48 for 4 level paging)

#

then the HHDM starts at 0xFFFF800000000000 (also the end of non-canonical address space for 4-level paging)

#

not sure how long that should go for

#

I guess to 0xFFFF900000000000 should be plenty

#

that's 1<<44 of space

hollow trail
lost schooner
#

never looked it up

hollow trail
lost schooner
#

thanks

hollow trail
# 
 ffff888000000000 | -119.5  TB | ffffc87fffffffff |   64 TB | direct mapping of all physical memory (page_offset_base)
lost schooner
#

in this, where is general purpose kernel memory?

#

is it all the unused holes?

hollow trail
#

ffffc90000000000 | -55 TB | ffffe8ffffffffff | 32 TB | vmalloc/ioremap space (vmalloc_base)

lost schooner
#

nevermind

#

just saw that

#

I won't copy this exactly, but I'll use it as a rough guide

hollow trail
#

yeah i dont think u need LDT remap for PTI

#

etc

lost schooner
#

I don't understand the point of all the holes, especially the 8TB one at the beginning of the second part of canonical address space

hollow trail
#

who knows

lost schooner
#

I think there is a mistake in the non-canonical space for 5 level tables

#

and there is more space allocated for physical memory than what is supported

#

the maximum theoretical physical memory size is 4PiB (1<<52), but the linux map allocates 32PiB (1<<55)

hollow trail
#

maybe they just reserve more for the future

#

128 bit page tables will support more

lost schooner
lost schooner
#

which means HHDM goes to 0xFFFFC00000000000

#

which is 64TiB of maximum theoretical physical mapping space

#

with current computers, that is way more than what is needed

#

for the majority of computers anyway

#

then I think until 0xFFFFF00000000000 should be for virtual memory allocation

#

then from there until 0xFFFFFFFF80000000 is unused

#

then from there until the end of address space is for the kernel's ELF segments and any modules in the future

lost schooner
#

this code segment should hopefully show what I mean by all this:

image.png
#

its a little messy due to those functions taking a start address and page count

#

I'll write proper docs for this somewhere

lost schooner
#

couldn't work on this at all yesterday

#

Just wrote these docs in the arch specific paging init header file:

image.png
#

wait thats not very consistent

dusky orbit
#

'arch specific', are you planning to go multi arch?

lost schooner
#

thats better:

image.png
lost schooner
dusky orbit
#

cool ๐Ÿ˜„

#

any idea what your first port will be?

lost schooner
#

not exactly sure, but the only non-x86 hardware I have is aarch64 and arm-v7

#

I have 1 raspberry pi 3B+ 2GB, 2 raspberry pi 4B 4GBs, an aarch64 phone (will not be used for any form of testing though), and an old arm-v7 tablet

dusky orbit
#

testing on your phone would be bold lol

lost schooner
#

yeah, won't be testing on my phone, just listing devices

lost schooner
#

I don't know why that came as a surprise

#

everything is cleaned up and ready to be committed

#

alright, time to move on to the PageManager

lost schooner
#

I've implemented some PageTable abstraction in a way that doesn't use any ifdefs

#

I liked what I did in my old kernel page manager where I had an AVL tree of regions, sorted by address

#

So I'm going to do that again

sand scaffold
#

To manage allocated address regions?

#

That seems standard, but go for it

lost schooner
#

I've just implemented a temporary OOM handler which for now just calls PANIC

#

having a proper function early is better than later removing random PANICs in the PMM

lost schooner
#

I now have a basic PageManager implementation

#

I will need to expand on it a bit to support lazy physical allocation and eventually shared mapping

#

I'm scared to test the current code

#

because every time I test something, I get so many bugs

lost schooner
#

stupid nvidia driver keeps making vscode freeze

#

not a good start to testing:

image.png
#

why is something calling kmalloc

#

ohhh

#

so stupid

#

forgot to set the AVLTree into VMM mode

#

now I get a GPF

#

forgot to mention that it is pretty much the same test I've been using for everything else

lost schooner
#

specifically FreePage

#

looks like a dodgy address is being parsed to that function

#

it is called by x86_64_UnmapPage

#

oh I see the issue

#

forgot to convert a HHDM address back to a physical address

#

after only 18k iterations I get an OOM

#

that shouldn't be happening

#

maybe stuff isn't being freed properly

lost schooner
#

this time it was 30k

#

free is definitely working

#

maybe there just isn't enough physical memory for this test

#

I'll have to modify the test a bit to store the size of each allocation

#

yeah, I can confirm that I need to scale down the maximum allocation size or increase the RAM size

#

I think I'll go with just halving the maximum allocation size

#

that still wasn't enough to make it through the whole test

#

I'll also up the RAM size I guess

#

and it was successful

#

it does seem to slow down a bit when there is a lot of allocations, but realistically, I doubt that 1 instance will constantly have 150-200+ allocations at once

#

it is most likely the page mapping slowing things down

#

but once again, realistically, there isn't going to be constant 200-500 page allocations

#

I will eventually add larger page support to the PMM and VMM

#

which will help with that possibility

#

I have it implemented in the PageTable, but not the PMM, VirtualMemoryAllocator or PageManager

lost schooner
#

just so I can do it properly

#

instead of hacking together something messy now

#

I'm going to clean this up, get it committed then I guess I'll do the kernel heap?

#

which will be another instance of the HeapAllocator, so no actual testing is needed

lost schooner
#

alright, kernel heap time

#

the kernel heap is fast

#

with KVM on, a looked away for a couple of seconds waiting for OVMF to load, and it had done 100k iterations

#

no verify, but I have already thoroughly tested the HeapAllocator, so there isn't much point

#

I'll quickly do an eternal heap, then this will be done

#

and it is done

#

I went with a size of 2MiB or 512 pages

#

which is way more than what will probably ever be needed, but just to be safe

#

IRQ system was next on my list

#

but I might do kernel symbol parsing first

#

idk

#

I'll think about it

lost schooner
#

I just realised something

#

In my old kernel, it took me 7 months to get close to this point. In my current kernel, its taken ~6 weeks

#

I started the rewrite on the 17th of august

#

Its been 50 days

#

Or ~7 weeks

dusky orbit
lost schooner
#

That's what I was doing

dusky orbit
#

ah, not a fan of that idea?

lost schooner
#

No

dusky orbit
#

oh I see, I understand your prior message

#

the random panics

lost schooner
#

Makes more sense to me to handle it the same in all situations, instead of leaving the caller responsible

dusky orbit
#

I disagree, but I can see the logic there

#

also cool to see more testing of your kernel

lost schooner
#

I was busy during the week || definitely not just watching stuff on disney+ ||

lost schooner
#

I was going to work on this today, but I managed to brick my windows install whilst trying to move it to another drive, so I'm clean installing.

#

Luckily arch was unaffected

lost schooner
#

alright, time to return

#

I want to make more debugging information available to the user during a kernel panic

#

the first step is symbol parsing

#

in my old kernel I tried to simplify the symbol table before runtime to make it easier on the kernel

#

the simplified format was just this:

  1. raw address
  2. 0x00
  3. name
  4. 0x00
#

which worked alright, but ubsan didn't like it

#

due to the unaligned 8-byte reads

dusky orbit
#

have you thought about parsing the elf symbol table?

#

the only downside is you'll get mangled names

lost schooner
#

i only want demangled names, so I don't think I like that option

dusky orbit
#

fair

#

I have a freestanding version of libiberty's demangle code, but its like 4K loc

#

reminds me I need to finish cleaning that up

#

so what are you thinking, store the symbol info at the end of the kernel?

lost schooner
#

no, a limine kernel module

lost schooner
#

I just made a simple 73 loc C++ (could be C) file which just removes the extra space and character between the address and symbol name in the nm output

#

I might also add duplicate symbol removal

#

I'll make it so it uses the last symbol at an address

#

actually nevermind

#

too much effort

lost schooner
#

I want to try make a hash map implementation for this, but I don't know how they are supposed to work

#

I know that I could create a super simple one which uses a linked list, but I feel like that isn't the proper way

lost schooner
#

It appears that the libstdc++ in GCC uses a rb tree

lost schooner
#

I'll just use an AVL tree since I already have an implementation

#

Actually, I wont bother with a hash map. I'll just use an AVL tree directly

lost schooner
#

this doesn't look right:

image.png
#

all of the symbols seem to be added to the table correctly

#

oh wait

#

stupid mistake

#

I really should add some attribute to my printf so GCC warns me about bad args

#

there we go:

image.png
#

even better:

image.png
lost schooner
#

next is IRQ system

#

I'm not starting that tonight though

dusky orbit
#

nice

lost schooner
#

first part is going to be SMP

#

then proper IPIs

#

then I/O APIC stuff

#

I might experiment with going from real mode straight to long mode

lost schooner
#

It seems like the PML4 has to be under 4GiB so I can actually load cr3

lost schooner
#

I think I might have a working AP trampoline

#

it triple faults

#

not a good start

#

I added -no-reboot and -no-shutdown, but it still just reboots

#

that's weird

#

it dies on the INIT

#

doesn't even do an SIPI

#

it seems to be trying to do it on the BSP

#

I don't know why though

#

I see the problem

#

for some stupid reason, the initial LAPIC code was assuming the BSPs LAPIC id was 0

#

so when I changed the default to be 0xFF instead of 0, it broke everything

#

so I should be getting the BSPs ID from CPUID I believe

#

it gets further now

#

the BSP somehow tries to execute 0xfec0000000000c01

#

with no stack trace

#

not sure how that happened

#

oh I see

#

now it appears like an INIT and SIPI are sent, but nothing happens

#

and there is a bogus MADT entry

#

I forgot to add a second CPU

#

it still doesn't work

#

I remember something about there needing to be a delay between the INIT and SIPI

#

but I don't have a timer

#

I tried a 100 million iteration for loop in between the INIT level desassert and SIPI as a replacement just to test

#

and nothing changes

#

even a 1 billion iteration for loop doesn't do anything

lost schooner
#

I should probably just make a timer interface first

#

which means I/O APICs

lost schooner
#

For timers, I guess I'll do PIT and HPET

#

Since QEMU doesn't put a PIT device in the ACPI namespace, even though it exists, I could probably just assume its existence

#

I remember someone saying that linux does that

lost schooner
#

For some reason I was assuming that the length of a MADT entry was fixed

hardy lake
#

that defines that

lost schooner
#

Idk

hardy lake
#

bit something

#

ACPI_IA_PC_LEGACY_DEVS

#

and you can further detect the ps/2 controller by checking the ACPI_IA_PC_8042 flag

# 
#define ACPI_IA_PC_LEGACY_DEVS  (1 << 0)
#define ACPI_IA_PC_8042         (1 << 1)
#define ACPI_IA_PC_NO_VGA       (1 << 2)
#define ACPI_IA_PC_NO_MSI       (1 << 3)
#define ACPI_IA_PC_NO_PCIE_ASPM (1 << 4)
#define ACPI_IA_PC_NO_CMOS_RTC  (1 << 5)```
#

these are all the flags

#

and the flags in the acpi spec

image.png
lost schooner
#

Ok

hollow trail
#

you're using uacpi right? it has those flags defined in acpi.h

#

linux uses PIT unconditionally, it doesnt check those tho

lost schooner
#

so, I'll do lapic improvements, and I/O APIC, commit it

#

Then I'll do a uacpi port

#

then timer interface

#

just discovered a bug where the BSP's LAPIC isn't actually being enabled

#

I might actually leave the I/O APIC until after the uacpi port

#

I won't commit these LAPIC improvements on there own

#

I'll just start on using uacpi again

lost schooner
#

and all the functions that I can implement are implemented

#

just need to migrate the existing ACPI code to use uACPI instead

lost schooner
#

uacpi init has changed a bit since I last used it

#

I don't know how to set the log level anymore

#

I think I need to call uacpi_context_set_log_level before uacpi_initialize?

#

I don't have mutexs yet, so I had to do this to get uacpi to actually initialise:

image.png
lost schooner
#

this isn't good:

image.png
#

maybe I should have done some more testing on the kernel heap

#

I tried running the heap test on its own, and I get an OOM

#

I think something is off here...

image.png
#

there shouldn't be an OOM:

image.png
#

there is plenty of free memory

#

something is very wrong:

image.png
#

I'll start with the heap issue and then go from there

#

because it could be causing this

#

I just checked the VMM heap, and it is unaffected, which means that the page manager could be responsible

#

yep, it appears to be

#

I'll need to test a bit more to confirm this though

#

ohhh

#

I forgot that the test needs more than the normal 256MiB of RAM

#

the page manager is fine

lost schooner
#

I couldn't work on this at all yesterday due to being stuck at school for 14 hours....

#

After I checked that the page manager was fine, I went back to testing the kernel heap

#

It seems to cause an OOM very fast

#

So I'm suspicious that something is not freeing properly

dusky orbit
#

Damn school days have lengthened since I attended

hollow trail
lost schooner
#

I had to stay after school to do stuff for a music concert

lost schooner
#

time to sort out this OOM

#

my first thought was that bad regions were being given to PageManager::FreePages, but they aren't

#

this isn't directly related, but for some stupid reason, the kernel .text section is being mapped as Read/Write/Execute

#

only 194 virtual pages are allocated in kernel address space

#

so where are all the physical pages disappearing to

#

I wonder how big the VMM heap is

#

only 36864 bytes

#

the used memory variable in both the VMM and kernel heaps is very wrong

#

the free and metadata variables in both heaps are also wrong

#

there must be some case(s) where I forgot to add/subtract from them

#

I have found some incorrect locking, but no bad addition/subtraction

#

well I found it

#

numbers are still wrong, but not as bad

#

the used mem for the VMM heap is -258192

lost schooner
#

Time to continue debugging this

lost schooner
#

I found a tiny hidden bug

#

it occurs only a certain edge case where a chunk has a size of precisely size + sizeof(BlockHeader)

#

chunk with one block that is

#

I meant that the only block in a chunk has precisely that size

#

for some reason the next chunk isn't being set

#

it was detected by the total number of free memory in the list not matching the variable

#

I just found another mismatch

#

this time in free

#

this one is where the recently freed block has become the last block in a chunk

#

but is not exactly after the old last free block in the chunk

lost schooner
#

this basically confirms that something is disappearing from the list:

image.png
#

at entry 4032 bytes are free

#

at exit, 4928 bytes are reported and 3888 are actually

#

it is a free, so that number shouldn't decrease

#

the reported appears to be correct

#

but the actual is wrong

#

so something is being taken out for case 2.2

#

this is the problematic code:

image.png
#

wait

#

I see the problem

#

current must be less than header

#

so prev isn't relevant

#

sort of anyway

#

wow the simple fix I did made the test get a lot further

#

there is still a bug somewhere though

#

looks like it is in allocate this time

#

the issue appears to be a block's size exceeding the size of its chunk

#

oh no

#

that block shouldn't even be in that chunk

#

looks like the isLastBlock member variable isn't being set properly

#

it was set correctly, just weirdness was going on

#

which is now fixed

#

but I'm back to getting an OOM

lost schooner
#

I don't understand how or why it OOMs

#

the kernel heap is 192512 bytes, and the VMM heap is 12288 bytes

#

the kernel heap has 139296 bytes of used memory

#

the test is using 25040 of that

#

if that is correct, kernel symbols are using 114256 bytes

#

which might be true

#

there are ~1400 symbols

#

so that is definitely possible

#

but why is it running out of physical memory

#

it should have 1GiB

#

there is 0x2f pages mapped in allocatable kernel address space

#

that's only 188KiB

#

so where is all the physical memory disappearing to

#

I think there might be a bug in the PMM

#

those numbers are wrong

#

I think

#

the free mem one anyway

#

looks like I might be testing the PMM again

lost schooner
#

I think that 100 million test iterations might be too many...

#

oh well

#

its done ~60 million, so I might stop it there

#

it was only single page allocation/free

#

I'll try doing multi-page

#

I'll do a maximum of 256 pages

#

a maximum of 1024 regions can be allocated at once

#

giving a maximum theoretical usage of exactly 1GiB

#

but, it shouldn't get too close to that

#

I'm going to disable OOM detection for this and just return nullptr

#

and it just works

#

I've tried overwriting the first part of the page region so that any metadata is unusable

#

and it still works

#

I can't reproduce the issue

lost schooner
#

the test finally finished

#

so I have no idea what the problem is

#

all these stupid memory management bugs are really annoying me

#

my motivation for this is really low at the moment

#

I might work on some other projects for a bit until I feel motivated again

dusky orbit
#

fair enough, no fun in burning out - anything in particular you want to work on?

lost schooner
#

I'm going back to working on my custom cpu architecture

lost schooner
#

its been a fair bit

#

still not quite ready to return

#

but will soon

lost schooner
#

I think it might be time I return

#

I need to work out why the PMM only stuffs up when running the kernel heap test, and not when running it's test

#

I've changed the PMM test to only allocate 1 page at a time, but with a much higher maximum number of allocations

#

i modified it even further so that frees only happen 25% of the time

#

might need to modify that a bit though

#

I changed it to 40%, and its slightly better

#

with 50% of each allocate and free, not that many pages would be mapped at once, so it isn't similar to the heap test

#

40% being free still isn't that good either

#

45% is better

#

I can't go for 50% though

#

i'm just going to run the heap test again

#

what

#

the test passes?

#

how

#

this is really strange

#

kvm was on