Jeff BezOS | Operating System Development | Page 3

nova fiber Apr 17, 2025, 11:26 PM

#

oh and i can now emulate reads and writes to cr3 in my test harness

#

i'll do actual paging emulation soon i suppose

urban schooner Apr 18, 2025, 12:35 AM

#

Wait you wrote an x86 emulator for testing your kernel?

nova fiber Apr 18, 2025, 1:04 AM

#

Sorta

#

Its closer to paravirtualization

#

I use signal handlers and ptrace to single step execution and capture side effects

#

So like rdmsr, wrmsr, changing page tables, doing mmio

nova fiber Apr 18, 2025, 1:28 AM

#

i think qookie originally suggested using ptrace and self debugging

#

very good suggestion

#

completely insane execution on my part but i cant argue with the results

nova fiber Apr 18, 2025, 3:08 AM

#

hm i think im going to have to start ref counting pages

#

sharing mappings without leaking stuff or holding onto alot of extra memory is a bit tricky

nova fiber Apr 18, 2025, 3:29 AM

#

i think tomorrow i will move the elf loader into a shared project between the userspace and kernelspace

#

will be a little wonky to write but whatever

urban schooner Apr 18, 2025, 7:07 AM

#

nova fiber I use signal handlers and ptrace to single step execution and capture side effec...

Damn

#

What sort of stuff do you test with it

nova fiber Apr 18, 2025, 2:54 PM

#

urban schooner What sort of stuff do you test with it

right now i use it to test that context switching correctly changes page tables and the tls address, i also test my apic, x2apic, and ioapic code with it

#

i'd like to eventually test interrupts with it by using pthread_sigqueue

#

and at some point test paging by using memfd_create and some clever use of mmap and mprotect

#

oh fun thing about this is that it exposes bugs in linux's zram kernel module meme

#

zram doesnt page in stuff correctly if you use mprotect inside a signal handler so you always read back FF

urban schooner Apr 18, 2025, 7:09 PM

#

Damn

#

Feels a tiny bit overkill lmfao

nova fiber Apr 18, 2025, 7:27 PM

#

possibly meme

nova fiber Apr 19, 2025, 9:23 PM

#

rtld can now launch statically linked processes in userspace so thats progress

#

although the mmap code is a real mess so i think its time to write that paging test harness and get that sorted out

#

and maybe finally get that tlsf implementation for physical memory working

#

and pthread_sigqueue to try and track down some of the deadlocks im having

#

if im feeling abitious i may be able to test actual context switches by handling the #GP from iretq

#

and msr access to gsbase and fsbase

#

oh unrelated but got xdrpp building for the package tool

#

havent integrated it yet

nova fiber Apr 20, 2025, 2:57 AM

#

ok so i think for emulating paging i'll need to fork a process for each emulated cpu core, create a shared memfd file, then trap on writes to cr3 and sigsegv to map the memfd into each processes address space as needed

#

shouldn't be too hard i dont think

#

sharing test data is going to be a bit annoying, although if CLONE_VM behaves how i think it does then that also might be fine

prisma stirrup Apr 20, 2025, 3:01 AM

#

Admittedly I've only skimmed, but why create an emulator instead of fiddling with qemu? Or does the emulator runs as a user program in your os?

nova fiber Apr 20, 2025, 3:01 AM

#

doing unit testing inside qemu would be really hard

#

doing it on the host machine means i have access to better debug tools, can use valgrind, get coverage reports, and can write 200 tests for a single thing without having to spin up alot of vms

#

its also alot quicker to run a unit test than launch qemu, my ioapic tests run in 140ms which is orders of magnitude faster than just launching qemu

prisma stirrup Apr 20, 2025, 3:10 AM

#

Cant argue with speed, though all host debugging tools would be attached to your emulator

You could use a common snapshot for all of your tests, and automatically restart from snapshot and choose a different run, it's going to be a lot slower then a dedicated emulator but you'd avoid the need to debug emulator problems and youd have a lot more capability to teat different things

#

Though writing an emulator is definitely interesting and thats a worthy goal on its own

nova fiber Apr 20, 2025, 3:12 AM

#

honestly debugging the emulator after the initial debug register setup hasnt been too bad, although i have been looking at using qemu or virtualbox source code to emulate some of the devices for me

nova fiber Apr 20, 2025, 3:12 AM

#

prisma stirrup Though writing an emulator is definitely interesting and thats a worthy goal on ...

i will admit this is also a bit of a curiosity for me lol

prisma stirrup Apr 20, 2025, 3:17 AM

#

Can't vouch for virtualbox but qemu is very clean and easy to get your bearing once you get what they're doing with memory mapping and their objects registration

nova fiber Apr 21, 2025, 12:57 AM

#

i have spent 8 hours attempting to get code coverage for 5 lines in my allocator

#

i cannot for the life of me reach this codeblock in a test case

sour geyser Apr 21, 2025, 1:06 AM

#

Remove them meme

nova fiber Apr 21, 2025, 1:06 AM

#

i hit it in regular usage pain

#

i havent a clue what obscure sequence of allocations i need to do to hit that block though

#

i swear im going to end up implementing fuzzing just for this

nova fiber Apr 21, 2025, 1:51 AM

#

hrn good enough for now i guess

#

i've got 100% branch and state space coverage aside from that function

#

now to finally kill off my old pmm

#

actually not quite, forgot to add dynamically adding memory to the heap

nova fiber Apr 21, 2025, 5:12 PM

#

ok got that done, also added grow and shrink

#

cant do realloc since the backing memory is inaccessible, so moving the block is impossible

nova fiber Apr 22, 2025, 2:59 PM

#

Oh i think i'll also need to implement allocation splitting

#

Since i refcount pages at whatever granularity the range was allocated at i need to be able to split an allocation if two processes map overlapping areas of memory

#

retaining an entire 2gb allocation because a process has 4k of it mapped seems not so great

zealous mirage Apr 22, 2025, 5:06 PM

#

nova fiber retaining an entire 2gb allocation because a process has 4k of it mapped seems n...

this is one of the difficulties of large pages

#

it's one thing if it's small multiples like 64k. then if you're replacing pages, it's not a huge waste if someone only cares about 4k of it and doesn't touch the other 4k component pages

#

but if it's 2mib and you retain 2mib worth of data when someone is only ever touching 4k of it you have a big waste

#

(this is a page replacement rather than allocation specifically problem but a big one)

nova fiber Apr 22, 2025, 5:54 PM

#

zealous mirage it's one thing if it's small multiples like 64k. then if you're replacing pages,...

im trying to avoid anything with space complexity where N is related to the size of the managed data which probably makes this more complicated.

#

im not a fan of the idea of fixed overhead associated with just using a resource like memory

#

i was originally going to associate a 16 bit counter with each 4k page which is only 0.04% memory overhead, but then scaling that up it feels bad to waste a whole 16gb of ram just to count pages on my desktop

#

i think that the correct choice for an OS is usually to optimize for space complexity of data rather than optimize for speed within reason

nova fiber Apr 22, 2025, 5:59 PM

#

nova fiber im trying to avoid anything with space complexity where N is related to the size...

unless O(N) is really really tiny

#

my tlsf heap technically has O(N) space requirements for its freelist, but to handle 2tb of memory the freelist is only 5kb so im not too worried

nova fiber Apr 24, 2025, 7:30 PM

#

https://rigtorp.se/isatomic/ devilish

Aligned AVX loads and stores are atomic

On the latest CPU microarchitectures (Skylake and Zen 2) AVX/AVX2 128b/256b aligned loads and stores are atomic even though Intel and AMD officially doesn’t guarantee this.

#

god is this tempting to abuse

#

256 bit atomic loads and stores

#

some intel chips even have atomic 512 bit loads and stores

brave cape Apr 24, 2025, 8:10 PM

#

nova fiber i was originally going to associate a 16 bit counter with each 4k page which is ...

what sort of NASA computer do you have if 0.04% of your RAM is 16GiB??

nova fiber Apr 24, 2025, 8:10 PM

#

oops thats 4% i missed a decimal place

#

my bad

#

160 megabytes my bad

brave cape Apr 24, 2025, 8:12 PM

#

160 megabytes out of how much, like 64 GiB or something? that is negligible.

nova fiber Apr 24, 2025, 8:12 PM

#

398gb

#

still feels wrong to just eat the memory when i could instead not

brave cape Apr 24, 2025, 8:12 PM

#

even more negligible then

#

do you not have a struct page?

nova fiber Apr 24, 2025, 8:14 PM

#

no

brave cape Apr 24, 2025, 8:14 PM

#

so where is linkage for e.g. page cache pages?

nova fiber Apr 24, 2025, 8:15 PM

#

right now i have no disk drivers so i just havent gotten around to that

brave cape Apr 24, 2025, 8:20 PM

#

at some point, you will probably need linkage for the pages somewhere for LRU and additionally per-page refcounting and locking for IO. now, if you really don't like struct page, you can store it in e.g. an array per memory object, where a "memory object" is e.g. a filesystem-backed mmapable file or anon, possibly shared memory. but a struct page is just convenient for this type of thing.

nova fiber Apr 24, 2025, 8:22 PM

#

i'll have something like that eventually, just with granularity thats based on the size of the allocation rather than per-page

brave cape Apr 24, 2025, 8:23 PM

#

splitting allocations will probably become harder as a result of no per-page linkage and refcounting etc. IMO it is already hard enough

brave cape Apr 24, 2025, 8:24 PM

#

nova fiber i havent a clue what obscure sequence of allocations i need to do to hit that bl...

have you solved this yet?

nova fiber Apr 24, 2025, 8:25 PM

#

after alot of testing i've concluded its now dead code

#

its a private function and i changed the callsites enough thats its no longer hit

brave cape Apr 24, 2025, 8:26 PM

#

nova fiber i hit it in regular usage <:pain:679047090474713098>

if you would hit it in real usage but not in your testcases, something that you might do is to dump allocations over 0xe9 or something ("record and replay")

nova fiber Apr 24, 2025, 8:27 PM

#

i cant hit in real usage either now lol

brave cape Apr 24, 2025, 8:27 PM

#

lol

#

so are you just going to replace it with assert(!prev->isFree());?

nova fiber Apr 24, 2025, 8:28 PM

#

pretty much

nova fiber Apr 24, 2025, 11:06 PM

#

more thorough testing of the tlsf heap has revealed even more bugs

#

wow i suck at writing allocators

#

thank god for gcovr

nova fiber Apr 25, 2025, 4:26 AM

#

i think i hammered out all the bugs for now

#

im sure i'll find new ones tomorrow though meme

nova fiber Apr 25, 2025, 6:22 PM

#

https://cor3ntin.github.io/posts/clang21/#constexpr-all-the-things-asm-edition

#

what a treat

umbral grotto Apr 25, 2025, 6:24 PM

#

nova fiber what a treat

What in the world

#

Like

#

Why are you giving it string views

#

asm is not a function

nova fiber Apr 25, 2025, 6:24 PM

#

you can give a static assert a string view for its message at compile time

#

you can now do the same with asm

umbral grotto Apr 25, 2025, 6:24 PM

#

"this would be useful for people writing SIMD libraries. You could also use it to write a C++ compiler in C++."
no shit

#

you could already do that

nova fiber Apr 25, 2025, 6:24 PM

#

you can also give it a plain string as long as its constexpr evaluated

umbral grotto Apr 25, 2025, 6:25 PM

#

aren't plain strings uh

#

constexpr evaluated already?

nova fiber Apr 25, 2025, 6:25 PM

#

sorry i meant std::string

umbral grotto Apr 25, 2025, 6:25 PM

#

oh std::string

#

but why would you give asm anything but a plain string

#

i do not get it

nova fiber Apr 25, 2025, 6:26 PM

#

so you can generate asm dynamically based on parameters

#

like generating different avx instructions depending on if you're working with 128bit or 256bit vectors

#

its a little insane either way, but could be fun to abuse

#

constexpr std::string GenerateIsrTable() {
  std::string isrs;
  for (size_t i = 32; i < 255; i++) {
    isrs += std::format(
      ".align 16\n"
      "AsmIsr{}:\n"
      "  pushq {}\n"
      "  pushq {}\n"
      "  jmp AsmIsrEntry\n"
      , i);
  }
  return isrs;
}

asm(GenerateIsrTable());

#

C++ as a macro assembler

prisma stirrup Apr 25, 2025, 9:43 PM

#

That's cursed lmao

brave cape Apr 25, 2025, 9:45 PM

#

C++ as a macro assembler, what god intended higher-level languages to be.

#

this shows that we've made full circle and are back where C started

#

meme

nova fiber Apr 26, 2025, 2:38 AM

#

https://godbolt.org/z/hE6v99da3 perfect

Compiler Explorer - C++

consteval std::string GenerateIsrTable() {
std::string isrs;
for (size_t i = 32; i < 255; i++) {
fmt::format_to(
std::back_inserter(isrs),
FMT_COMPILE(
".align 16\n"
"AsmIsr{0}:\n"
" pushq {0}\n"
" pushq {0}\n"
" jmp AsmIsrEntry\n")
, i);
}
return isrs;
}

constexpr auto test = Gener...

#

aside from timing out godbolt

nova fiber Apr 26, 2025, 3:29 AM

#

in os related news the process vmm is coming along

#

i now no longer leak all allocated memory meme

#

i properly split physical page ranges as needed to correctly track owner counts

#

i will need to add some more apis to my allocator and page table manager to support doing multiple operations at once to guard against out of memory situations

#

right now its possible to oom during an operation and leave stuff in a slightly busted state

#

i also once again have mapping another processes address space working, and now it also only maps the areas that the other process has mapped

nova fiber Apr 26, 2025, 3:51 AM

#

and also follows the mappings if the other program has mapped a file or whatever

nova fiber Apr 26, 2025, 1:41 PM

#

nova fiber https://godbolt.org/z/hE6v99da3 perfect

https://godbolt.org/z/rcahb4W6W the technology isnt there yet unfortunately

Compiler Explorer - C++

consteval std::string GenerateIsrTable() {
std::string isrs;
isrs.reserve(0x10000);
for (size_t i = 32; i < 34; i++) {
fmt::format_to(
std::back_inserter(isrs),
FMT_COMPILE(
".align 16\n"
"AsmIsr{0}:\n"
" pushq {0}\n"
" pushq {0}\n"
" jmp AsmIsrEntry\n")
, i);
}
return isrs;
}

asm...

#

lowering the generated asm size makes clang explode

nova fiber Apr 26, 2025, 11:00 PM

#

today has been one long bruh moment

#

implemented transactional tlsf heap updates, transactional page table updates, and made a whole heap of stuff resilient to oom by using that

sour geyser Apr 27, 2025, 12:33 AM

#

That's pretty cool

nova fiber Apr 27, 2025, 2:28 PM

#

im not looking forward to writing a transactional b-tree and b+ tree

nova fiber Apr 27, 2025, 10:05 PM

#

small poll to anyone who cares to respond: if you mapped a processes address space into your own, and the range you requested to map either didnt start in a mapped area, or contained holes of unmapped memory. how would you expect the mapping to behave? should the mapping always fail if there's holes, only fail if the beginning of the range isnt mapped, only fail if nothing would be mapped?
diagram provided to visualize

#

horitontal bar is the requested memory to map, shaded blocks are mapped in the process, unshaded blocks are unmapped

#

second question, if a processes address space is mapped into your own and the process dies should the memory remain mapped with whatever was there when the process exited, should there be a SIGBUS signal equivalent like posix does with removed media, silently unmapped, reprotected as noaccess?

olive musk Apr 27, 2025, 10:08 PM

#

nova fiber small poll to anyone who cares to respond: if you mapped a processes address spa...

I would expect it to fail

#

As the request cannot be fulfilled (i.e. I wanted a mapping of size X, and it is not of size X)

#

And for the process dying thing, idk that is a good question

#

Both options would make sense

nova fiber Apr 27, 2025, 10:11 PM

#

olive musk As the request cannot be fulfilled (i.e. I wanted a mapping of size X, and it is...

hm fair, my current implementation maps the areas that have mappings and maps the rest as noaccess with no backing memory. but failing if theres holes definetly has less sharp edges and would probably make my implementation simpler as well

olive musk Apr 27, 2025, 10:12 PM

#

Your current way works too, it's a tricky question

prisma stirrup Apr 27, 2025, 10:31 PM

#

I would expect it to fail as well, otherwise every caller would have to be worried it succeed but not really.
2 can go either way I think, probably some unmapping would be required, perhaps unmap everything and treat the shared memory as if it was swapped out?

brave cape Apr 27, 2025, 10:32 PM

#

nova fiber small poll to anyone who cares to respond: if you mapped a processes address spa...

as in we have some process A and some process B, where process A does open("/proc/<B>/mem") or something, followed by mmap(NULL, 0x81000, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0x3000)?

#

this is very difficult to support.

#

it will probably mess with assumptions about non-shared memory (i.e. MAP_PRIVATE or MAP_ANON|MAP_PRIVATE)

nova fiber Apr 27, 2025, 10:33 PM

#

brave cape as in we have some process A and some process B, where process A does `open("/pr...

yeah basically

brave cape Apr 27, 2025, 10:34 PM

#

I would just not support mmap on that file

#

not worth the effort

nova fiber Apr 27, 2025, 10:34 PM

#

i mean i already support it lol, its how my rtld does program loading

brave cape Apr 27, 2025, 10:34 PM

#

??

#

please explain

nova fiber Apr 27, 2025, 10:35 PM

#

the rtld creates an empty process, then maps everything needed into the process, then creates a thread inside the new process

brave cape Apr 27, 2025, 10:36 PM

#

that's not what this is

nova fiber Apr 27, 2025, 10:36 PM

#

this way i dont need to make the rtld relocate itself, or do deduplication of shared libraries in the kernel

brave cape Apr 27, 2025, 10:36 PM

#

as I understand it, your rtld is effectively executing mmap in the context of another process

brave cape Apr 27, 2025, 10:36 PM

#

brave cape as in we have some process A and some process B, where process A does `open("/pr...

this is mmap another process' address space into oneself

nova fiber Apr 27, 2025, 10:36 PM

#

yes, it also has to map the other processes memory into its own process to write the relocations

#

plus setup of the tls and a few other bits

brave cape Apr 27, 2025, 10:38 PM

#

part of why this is hard is because there are no clear semantics that everyone "obviously" agree on. e.g. what if process A mmaps some pages from process B, but then process B changes those underlying pages? does the mapping in process A also update? and what if process C now comes along and mmaps a bit of process A into itself? it quickly explodes in complexity.

nova fiber Apr 27, 2025, 10:39 PM

#

i havent found that tbh, its got mostly the same semantics as shared mappings on a file

brave cape Apr 27, 2025, 10:39 PM

#

and what if process A mmaps a bit of process B into itself, while process B also mmaps a bit of process A into itself, creating a cycle?

nova fiber Apr 27, 2025, 10:40 PM

#

it'll all map to the same physical memory either way

brave cape Apr 27, 2025, 10:42 PM

#

spontaneously I would expect that it'd work in a way where if process A mmaps a bit of process B into itself, a page fault in A is handled by running the page fault handler as process B, taking the resulting physical page and plonking it into process A. then some kind of mmu notifier control mechanism so that whenever process B's page tables change, the entries in process A are cleared.

#

this becomes problematic if there are cycles.

nova fiber Apr 27, 2025, 10:43 PM

#

currently mapping a process just gets you a snapshot of whats currently mapped, if the subprocess updates a mapped area those changes arent reflected in the parent process

brave cape Apr 27, 2025, 10:44 PM

#

yeah that simplifies things substantially.

nova fiber Apr 28, 2025, 2:35 AM

#

oh dear

nova fiber Apr 28, 2025, 4:04 AM

#

pain misery suffering

#

1 gazillion edge cases

#

4k sloc of tests added in 2 days m_catdie

#

my internal design is definetly lacking in some ways but at least it works

iron mist Apr 28, 2025, 5:04 AM

#

nova fiber small poll to anyone who cares to respond: if you mapped a processes address spa...

I'd expect it to work the same way as mmapping a range of a file that goes beyond its bounds: the mmap call succeeds, but when accessing a page that isn't within bounds (or, in this case, mapped in the other address space) you get a SIGBUS

umbral grotto Apr 28, 2025, 12:08 PM

#

nova fiber small poll to anyone who cares to respond: if you mapped a processes address spa...

I would expect the access to fail in the same way it would when the process that's being mapped accesses the memory

#

When the process dies I would expect the mapping to continue working as it did while the process was alive

#

If I implement such a feature in Boron then that is how it will work

#

(Boron tracks user processes via the object manager so the process and its internal structures are only destroyed when that object loses all its handles)

#

(And the page map is destroyed in much the same way)

#

Now, mapping a process' address space into your own would add a reference to it so the process is still "kept alive" by virtue of you having mapped something from it into your own address space

nova fiber Apr 28, 2025, 1:15 PM

#

thank you all for the input him , you've given me much to think about! I will mull it over for a bit and make a final decision once I get all my tests passing

nova fiber Apr 30, 2025, 2:46 PM

#

https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p2900r14.pdf was finally accepted into the standard

#

i hope its implemented in clang somewhat soon, there is a fork with it implemented

#

my code is littered with a ton of asserts

prisma stirrup Apr 30, 2025, 2:56 PM

#

Its nice, but seems more like synthetic change that might not be adapted quickly

#

If it was assert on debug builds and assume on release builds it would be nicer imo

urban schooner Apr 30, 2025, 4:09 PM

#

nova fiber https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p2900r14.pdf was finall...

Is C++ Ada now

zealous mirage Apr 30, 2025, 4:48 PM

#

urban schooner Is C++ Ada now

it looks moreso inspired by Eiffel

nova fiber May 3, 2025, 1:46 PM

#

got the new memory stuff working

#

the code is a bit messy but it's got nearly 100% test coverage some im pretty confident it works for the most part

#

now to get testing interrupts working because my scheduler keeps deadlocking and forgetting tasks

#

I think i'd also like to run the build with clang time trace and do some cleanup of my build files because im recompiling some files 8 times due to permutations of test build flags

nova fiber May 3, 2025, 7:40 PM

#

figured out how to emulate a different page table per cpu core

#

abusing clone3 and an allocator inside a MAP_SHARED memfd

#

only the shared mappings are changed so i can do different mprotect and mmap calls per cpu core and they wont be visible

nova fiber May 4, 2025, 3:04 AM

#

thats new

#

funky

#

seems to work though

#

anyway thats enough for today

brave cape May 4, 2025, 9:38 AM

#

gregset_t :p

brave cape May 4, 2025, 9:38 AM

#

nova fiber funky

anyway you ought to mark ContextSwitchTestBody noinline; otherwise funky stuff can happen (especially if you do LTO)

#

I will also note that this code does not seem to do anything about the callee-saved (AKA non-scratch) registers. That is possibly a problem.

#

well, maybe PvTestContextSwitch does something that is non-obvious from the above code sample

nova fiber May 4, 2025, 12:32 PM

#

brave cape well, maybe `PvTestContextSwitch` does something that is non-obvious from the ab...

its just a full register context swap

#

im using it to test interrupts

nova fiber May 4, 2025, 12:38 PM

#

brave cape anyway you ought to mark `ContextSwitchTestBody` noinline; otherwise funky stuf...

LTO will see that a reference to the function body escapes analysis

#

it wont see that with a computed goto mind you, i tried taking a reference to a label and that was optimized away

#

urgh

#

only git has this problem

#

like i never lose actual data so im not sure what the deal is

#

the .git folder just ocassionally dies after a restart

prisma stirrup May 4, 2025, 12:55 PM

#

Maybe git executable shit itself? Odd

nova fiber May 4, 2025, 1:00 PM

#

this has happened on every computer i use and its consistently only ever git with this issue

#

its very odd

nova fiber May 4, 2025, 1:21 PM

#

anyway context switching for interrupts now works

nova fiber May 4, 2025, 5:06 PM

#

a bit scuffed but i can now emulate paging and smp

urban schooner May 4, 2025, 5:25 PM

#

The Greg Type

nova fiber May 5, 2025, 12:41 AM

#

https://tenor.com/view/house-md-dr-house-gregory-house-happy-dance-happy-gif-17229282564865713157

Tenor

#

found a lockfree priority queue

#

i think that should kill off a few more locks in the scheduler

nova fiber May 5, 2025, 2:41 AM

#

truly bleeding edge library

stone igloo May 5, 2025, 9:52 AM

#

nova fiber found a lockfree priority queue

is it any faster than not?

#

also

#

skip lists can be used as a lock-free sorted associative map as well and they are much more generic

nova fiber May 5, 2025, 2:58 PM

#

stone igloo is it any faster than not?

It's not about speed, it's about preventing deadlocks

#

Can't deadlock in the scheduler if nothing ever takes a lock

stone igloo May 5, 2025, 3:11 PM

#

lol

stone igloo May 5, 2025, 3:12 PM

#

nova fiber Can't deadlock in the scheduler if nothing ever takes a lock

i mean strictly speaking thats not true

#

but yeah fair

nova fiber May 5, 2025, 3:17 PM

#

OK yes wait free not lock free

#

But you know what I mean

nova fiber May 7, 2025, 3:35 PM

#

scheduler still deadlocks h_pain

#

I'm giving funqual another shot to see if i can get some better analysis than clangs rtsan can get me

#

somewhat related clangs consumable annotations let you implement substructural linear types and destructive move

#

#

in that example current is consumed by the RaiseIpl call, but since theres no ReleaseIpl call for dispatch its an error

#

slightly spastic code but this will get me some of the analysis i want

#

I can make nonreentrant functions take a special tag type as a parameter, then use that to ensure i dont accidentally call a function when i shouldnt be

#

if im feeling extra i could use the swift calling convention

#

since it removes empty types from the callconv

#

zero overhead™️

#

actually nvm the default clang calling convention also elides zero sized types

#

gcc doesnt though lol

nova fiber May 8, 2025, 12:14 AM

#

made scheduler deadlock a bit less

#

(i think)

nova fiber May 8, 2025, 4:07 PM

#

scheduler is still forgetting tasks i think

#

its very hard to debug if its a deadlock outside the scheduler or if its the scheduler itself forgetting stuff

#

not really sure where to start debugging this honestly

nova fiber May 8, 2025, 5:21 PM

#

im going to try and fix some of the bugs in funqual and use that to try and hunt down possible issues

#

it may actually be easier to use the existing clang function effects code and extend it to support more tags

#

although the clang one doesnt accept any kind of rules file, but that might not be impossible to add

nova fiber May 8, 2025, 7:54 PM

#

patching clang wasnt too hard

#

oh and bruh moment script of the day

#

function unfsck() {
    git fsck --full 2>&1 >/dev/null | grep 'error: object file' | awk '{print $4}' | tr '\n' ' '
}

#

because it happens at least twice a week

#

git just cannot handle wsl turning off i guess

urban schooner May 8, 2025, 8:46 PM

#

That's why I keep gitting on my windows drive and use wsl only for compiling

#

Very convenient with fork client

brave cape May 8, 2025, 9:23 PM

#

nova fiber ```sh function unfsck() { git fsck --full 2>&1 >/dev/null | grep 'error: obj...

s/s/u (fsck, unfsck)

nova fiber May 8, 2025, 10:13 PM

#

i've narrowed down my deadlocks to the scheduling and rcu queues

#

adding elements to them can allocate

#

so i think i'll move to fixed size scheduling queues and intrusive rcu object headers

nova fiber May 8, 2025, 11:34 PM

#

modifying clang to support reentrant and nonreentrant attributes was the right move i think, its much easier to track the state with automated lints rather than manually reading comments

nova fiber May 8, 2025, 11:58 PM

#

knowing how to modify the compiler of your preferred language has to be in the top 10 useful things when programming ngl

prisma stirrup May 9, 2025, 12:04 AM

#

Modifying dependencies in general is a great skill, though compiler is kinda taking it too far lmao

#

Modifying qemu helped me a ton

nova fiber May 9, 2025, 12:05 AM

#

yknow i actually havent found a need to modify qemu yet

#

i must not be using it wrong enough yet

#

i've done some horrible things to some of my other dependencies though lol

#

quite pleased with getting abseil building freestanding

#

the day of the btree creeps closer but i keep putting it off

prisma stirrup May 9, 2025, 12:12 AM

#

nova fiber yknow i actually havent found a need to modify qemu yet

I have so many modifications for debugging its quite insane - page walk, exceptions, irqs and so on. Most of the changes are temporary and allow for debugging qemu when it acts funny, or have bugs in tcg

#

Re-wrote the monitor terminal because it was written like 30 years ago and its infuriating to use, can't even search in history

brave cape May 9, 2025, 12:26 AM

#

prisma stirrup Re-wrote the monitor terminal because it was written like 30 years ago and its i...

are your patches available somewhere and do you plan on ever upstreaming anything?

prisma stirrup May 9, 2025, 12:27 AM

#

Sadly no, got a negetive response about publishing to upstream from management for now, unless its a critical bug.

brave cape May 9, 2025, 12:27 AM

#

😔

#

otherwise I find it likely that new contributors would be very welcome.

prisma stirrup May 9, 2025, 12:29 AM

#

Yeah contributing to qemu is nice after passing the mailing list problems

nova fiber May 9, 2025, 2:19 PM

#

mmm fun bug thats happened because i made my rcu lock free

#

in some of my destructors i was queuing things to be deleted later

#

this makes destroying the rcu domain recursively create more deferred objects to reclaim in some cases

#

oops

nova fiber May 9, 2025, 2:43 PM

#

good enough

nova fiber May 9, 2025, 4:47 PM

#

got the reentrant ringbuffer working as well

#

time to shove them into my scheduler

nova fiber May 9, 2025, 5:27 PM

#

seems to work

#

i think

nova fiber May 9, 2025, 6:34 PM

#

hmm fun bug

#

rax gets mangled during a syscall

#

and i havent the foggiest idea why

#

i am going insane

#

why is clang generating totally wrong assembly

#

oh i needed to use movq

trim owl May 9, 2025, 6:49 PM

#

is your code ```c
int arg0 asm("rax") = foo();
int arg1 asm("rbx") = bar();

nova fiber May 9, 2025, 6:49 PM

#

why wasnt that implicit from the operand size sade

nova fiber May 9, 2025, 6:49 PM

#

trim owl is your code ```c int arg0 asm("rax") = foo(); int arg1 asm("rbx") = bar(); ``` ...


PROC(OsSystemCall)
    mov %rdi, %rax /* syscall number */
    mov %rsi, %rdi /* arg0 */
    mov %rdx, %rsi /* arg1 */
    mov %rcx, %rdx /* arg2 */
    /* mov %r8, %r8 */ /* arg3 */
    /* mov %r9, %r9 */ /* arg4 */
    syscall
    /* rax:rdi */ /* return value */
    retq
ENDP(OsSystemCall)
```  was it

#

i needed to use movq rather than mov

#

rax is still changing to random values when entering my syscall handler but at least its not that i guess

trim owl May 9, 2025, 6:50 PM

#

strange

nova fiber May 9, 2025, 6:51 PM

#

bruh

#

does syscall clobber rax in some esoteric circumstance?

iron mist May 9, 2025, 6:52 PM

#

nope

nova fiber May 9, 2025, 6:52 PM

#

every other register is correct as well

#

only rax is wrong

trim owl May 9, 2025, 6:55 PM

#

maybe inspect the assembly at the OsSystemCall call site

nova fiber May 9, 2025, 6:57 PM

#

(gdb) disassemble/rs $rip
Dump of assembler code for function OsDebugMessage:
/sources/sysapi/src/bezos/syscall_debug.c:
5       OsStatus OsDebugMessage(struct OsDebugMessageInfo Message) {
   0x0000000000102c80 <+0>:     55      push   %rbp
   0x0000000000102c81 <+1>:     48 89 e5        mov    %rsp,%rbp
   0x0000000000102c84 <+4>:     48 83 ec 10     sub    $0x10,%rsp
   0x0000000000102c88 <+8>:     48 8d 75 10     lea    0x10(%rbp),%rsi

6           struct OsCallResult result = OsSystemCall(eOsCallDebugMessage, (uint64_t)&Message, 0, 0, 0);
   0x0000000000102c8c <+12>:    bf f0 00 00 00  mov    $0xf0,%edi
   0x0000000000102c91 <+17>:    31 c0   xor    %eax,%eax
   0x0000000000102c93 <+19>:    41 89 c0        mov    %eax,%r8d
   0x0000000000102c96 <+22>:    4c 89 c2        mov    %r8,%rdx
   0x0000000000102c99 <+25>:    4c 89 c1        mov    %r8,%rcx
   0x0000000000102c9c <+28>:    e8 4b 07 00 00  call   0x1033ec
=> 0x0000000000102ca1 <+33>:    48 89 45 f0     mov    %rax,-0x10(%rbp)
   0x0000000000102ca5 <+37>:    48 89 55 f8     mov    %rdx,-0x8(%rbp)

7           return result.Status;
   0x0000000000102ca9 <+41>:    48 8b 45 f0     mov    -0x10(%rbp),%rax
   0x0000000000102cad <+45>:    48 83 c4 10     add    $0x10,%rsp
   0x0000000000102cb1 <+49>:    5d      pop    %rbp
   0x0000000000102cb2 <+50>:    c3      ret    
End of assembler dump.
``` i *think* this is right

#

oh maybe im forgetting to preserve r15

nova fiber May 9, 2025, 9:59 PM

#

b KmSystemEntry if $rax = 0x31

#

im killing myself

#

fucking ==

#

aaaa

nova fiber May 10, 2025, 12:48 AM

#

i think im losing my mind

#

why is clang generating sldt instructions in normal code

nova fiber May 10, 2025, 3:48 AM

#

https://godbolt.org/z/q9qP1o8f4 funny clang flag of the day

Compiler Explorer - C++ (x86-64 clang (trunk))

[[noreturn]]
void ohno() {
__builtin_unreachable();
}

int main() {
ohno();
}

#

it is impossible to pass this flag to clang

#

but it will still suggest it to you

#

for some reason it just lets you disable all [[]] attribute syntax

nova fiber May 10, 2025, 4:46 PM

#

disabled ubsan and a test started failing SCeek

#

ubsan was initializing memory for me

#

lol, lmao even

nova fiber May 11, 2025, 8:12 PM

#

building gdb from source is kinda painful

#

it also builds with werror by default

#

so fuck you whoever chose that

#

also running make with any -j greater than 1 breaks the build which is extra retarded

nova fiber May 11, 2025, 8:55 PM

#

and the gdb it builds by default is broken

#

what joy

#

surely using the debian buildscripts will produce a functioning gdb Clueless

#

nope

#

someone should invent the fsf but with members that can comprehend the concept of UX and end user experience

#

it would seem you cannot have gdb installed in /usr/local if the folder /usr/share/gdb exists or it will explode

#

me when i dont respect prefix values during build or install

nova fiber May 11, 2025, 9:38 PM

#

god dwarf is infuriating

#

it behaves in strange ways and i cant for the life of me figure out why values change

nova fiber May 12, 2025, 1:53 PM

#

Backtraces through syscalls now sorta work

#

Only sometimes for some reason

#

I think i need to mark rsp properly in the cfi

nova fiber May 13, 2025, 12:46 AM

#

found the source of alot of my deadlocks

#

i really should've listened to the compiler warning

#

KmDebugMessage takes the message queue lock and this makes it nonreentrant

#

signal handlers need to be reentrant

#

// Takes a lock but this is probably fine was in fact not a correct statement to make

#

time to figure out how to log inside interrupts

#

shitty solution: add log messages to a buffer inside an interrupt, when outside an interrupt the next log flushes the pending messages

prisma stirrup May 13, 2025, 12:54 AM

#

The problem is nested interrupts? The log is per core right

Also "this is probably fine" is famous last words lmao

nova fiber May 13, 2025, 12:55 AM

#

the lock is global because it writes to the serial port

sour geyser May 13, 2025, 12:56 AM

#

Have you considered a two stage approach?

#

Write the logs to a buffer, someone else writes them to the outputs

prisma stirrup May 13, 2025, 12:56 AM

#

Ah then idk how adding directly to the buffer would help when the buffer write would need to be protected

sour geyser May 13, 2025, 12:57 AM

#

I do it with a try-lock whenever a log message is queued, if you take the lock you keep writing until the queue is empty (allows interrupts and other cpus to add messages in the mean time)

sour geyser May 13, 2025, 12:58 AM

#

prisma stirrup Ah then idk how adding directly to the buffer would help when the buffer write w...

You can do it locklessly

prisma stirrup May 13, 2025, 1:02 AM

#

Yeah you're right

sour geyser May 13, 2025, 1:02 AM

#

So you have head and tail pointers in the buffer, allocate by trying to compare exchange with the head pointer

#

Sorry I meant to elaborate earlier, got distracted

#

The problem I've run into, and it's quite possibly a skill issue, is the buffer filling up inside an interrupt or faster than the queue can be drained.

#

I imagine writing to the framebuffer and serial isn't helping, but a bigger buffer has solved that for now

nova fiber May 13, 2025, 1:17 AM

#

i have a good reentrant ringbuffer so thats probably the easiest option

#

this is also a good opportunity to move all my logging sinks out of main.cpp

#

where they have been since i started the project

umbral grotto May 13, 2025, 11:11 AM

#

nova fiber signal handlers need to be reentrant

Will a signal ever interrupt KmDebugMessage? Why?

#

Why do you need to log in interrupts anyway? If a good reason, then why not disable interrupts completely while printing?

iron mist May 13, 2025, 11:15 AM

#

NMIs usually need to be logged

#

or well, it's desirable to, anyway

umbral grotto May 13, 2025, 11:35 AM

#

iron mist NMIs usually need to be logged

that's a tough one for several reasons

#

what if an NMI interrupts your first

#

what if your logging routine is interrupted

iron mist May 13, 2025, 11:36 AM

#

nmis are masked from the time an nmi is first triggered to when an iretq is issued
that's why it needs to be reentrant

umbral grotto May 13, 2025, 11:36 AM

#

well, what I propose is that every NMI you increment a number or store some information, and right when you're about to exit to interrupt level zero, start logging

umbral grotto May 13, 2025, 11:36 AM

#

iron mist 1. nmis are masked from the time an nmi is first triggered to when an iretq is i...

how does it know you issue the iretq

#

and what if you never issue it

iron mist May 13, 2025, 11:37 AM

#

what is 'it' in this context? if it's the cpu, because it's the one executing it. if it's something else, it doesn't need to know, because the cpu masks it

umbral grotto May 13, 2025, 11:37 AM

#

umbral grotto how does it know you issue the iretq

oh wait is the NMI controlled by the CPU itself?

iron mist May 13, 2025, 11:37 AM

#

and if you never issue it nmis stay masked

nova fiber May 13, 2025, 10:48 PM

#

umbral grotto Will a signal ever interrupt KmDebugMessage? Why?

i want good visibility into whats going on, and i want my kernel to be hard realtime safe and therefore entirely preemptible outside of the scheduler

nova fiber May 17, 2025, 12:12 AM

#

new logger mostly works

#

its a bit boring

nova fiber May 17, 2025, 3:02 AM

#

the important message can be printed so im calling it for the night

nova fiber May 18, 2025, 1:44 AM

#

after significant soak testing i have made the unfortunate discovery that my ringbuffer is not entirely working

#

it only happens once in every like 50 test runs as well, and its only marginally broken

#

but damnit i thought i had tested it enough

#

made some slight tweaks and now its every 100 test runs rather than every 50

#

cmon man im 6 off

nova fiber May 18, 2025, 2:46 AM

#

I think i got it

#

eat your heart out freebsd my queue is better than yours frekw

nova fiber May 18, 2025, 2:28 PM

#

just for fun heres some benchmarks of the queue

#

copyobject is just the baseline

#

id say coming within like 20% of the baseline is pretty good for a queue, especially with like 64 threads all hammering it at once

#

wait wrong column

#

nvm this shit is ass lmao

#

made it significantly worse by padding things out to cache line size as well

#

pog

#

actually no i was reading the right column

#

the CPU time is misleading because its multithreaded

#

duh i suppose

#

it gets faster as theres more contention because the ringbuffer fills up and starts dropping messages pain

nova fiber May 18, 2025, 8:14 PM

#

clangd having another moment

nova fiber May 18, 2025, 11:07 PM

#

didnt know /usr/share/misc/pci.ids was a thing

#

quite useful

#

the things you can learn from running random shit under strace

#

I think i've migrated everything to the new logger now

#

now to get back to figuring out that damn dwarf backtrace info

calm shell May 18, 2025, 11:28 PM

#

whats your plan for blocking locks

nova fiber May 18, 2025, 11:29 PM

#

blocking locks? im not quite sure i understand. dont all locks block?

calm shell May 19, 2025, 12:27 AM

#

nova fiber blocking locks? im not quite sure i understand. dont all locks block?

spinlocks don't

#

they spin

#

block here means "block the thread"

nova fiber May 19, 2025, 12:28 AM

#

so like sleeping locks in linux?

#

right now i have a priority queue per object that can be waited or locked on and add stuff to that

#

its not great though

#

i should really switch to a linked list for the scheduler tbh

#

although the priority queue for waiting is useful for doing timeouts

umbral grotto May 19, 2025, 6:44 AM

#

nova fiber so like sleeping locks in linux?

i think so yeah

#

NT calls them "mutexes" (or mutants)

nova fiber May 19, 2025, 12:34 PM

#

yeah in that case i just take the thread out of the scheduler and put it onto a priority queue for the mutex

#

and then ocassionally look through the queues to find things with expired timeouts and add those back to the scheduler

#

really i should be using the apic deadline timer or something to get better latency but this is good enough for now lol

umbral grotto May 19, 2025, 1:23 PM

#

nova fiber and then ocassionally look through the queues to find things with expired timeou...

boron handles this by creating a wait DPC for the current thread, and a timer object which issues the DPC after a set amount of time. This DPC cancels the wait on the thread if it is still waiting

nova fiber May 19, 2025, 1:27 PM

#

that makes sense

umbral grotto May 19, 2025, 1:27 PM

#

as such there is no additional machinery that handles wait timeouts specifically

nova fiber May 19, 2025, 1:27 PM

#

my userspace facilities are really lacking ngl

umbral grotto May 19, 2025, 1:27 PM

#

same but I barely just reached userspace

nova fiber May 19, 2025, 1:27 PM

#

the process, threads, and whatnot i have are all pretty hacked together

umbral grotto May 19, 2025, 1:27 PM

#

I need to write a file system driver

#

Like, a proper disk based one, not a tmpfs thing

nova fiber May 19, 2025, 1:28 PM

#

i have a tarfs if that counts meme

umbral grotto May 19, 2025, 1:29 PM

#

tar is not a file system

nova fiber May 19, 2025, 1:29 PM

#

no actual disk drivers though lol

umbral grotto May 19, 2025, 1:29 PM

#

except if you're the osdev wiki for some reason

umbral grotto May 19, 2025, 1:29 PM

#

nova fiber no actual disk drivers though lol

I have an nvme driver

nova fiber May 19, 2025, 1:29 PM

#

damn

#

im not letting myself write any drivers until my userspace is functional enough to actually need them

#

and my userspace is shit and unstable hence no drivers

umbral grotto May 19, 2025, 1:30 PM

#

I feel like I need to get some drivers working first before I can truly start working on a userspace

nova fiber May 19, 2025, 1:30 PM

#

i figure theres no point in disk drivers if i cant open a text editor

umbral grotto May 19, 2025, 1:31 PM

#

umbral grotto I feel like I need to get some drivers working first before I can truly start wo...

Technically I don't, but I think it would be better this way

#

I have two ideas for userspace

#

One of them would be an mlibc based distribution

#

And another would be my own GUI and things

nova fiber May 19, 2025, 1:36 PM

#

you'll need a libc either way at least

nova fiber May 19, 2025, 1:53 PM

#

oh boy another hard to reproduce multithreaded issue

#

this time the rcu shared ptr i have does a use after free once in a blue moon

nova fiber May 19, 2025, 7:36 PM

#

I think my shared ptr might just be fucked

#

Damnit

nova fiber May 19, 2025, 9:36 PM

#

nvm that was easier than i thought

nova fiber May 19, 2025, 10:07 PM

#

scratch that

#

man this is a pain in the ass

brave cape May 20, 2025, 11:27 PM

#

RCU shared pointer?

nova fiber May 20, 2025, 11:41 PM

#

its an atomic shared pointer that uses rcu rather than a split reference count

#

which more importantly means that its reentrant, a split reference count isnt

nova fiber May 21, 2025, 3:36 AM

#

ah my generational rcu is buggered thats why

nova fiber May 21, 2025, 11:07 PM

#

userspace-rcu is more readable after being pre-processed than before

#

so much macro abuse

nova fiber May 21, 2025, 11:34 PM

#

nova fiber ah my generational rcu is buggered thats why

or not

#

i had written the test ever so slightly wrong

nova fiber May 22, 2025, 12:06 AM

#

please dont tell me i wrote the shared ptr tests wrong in the same way

#

god fucking damnit

#

there was no bug i was just a rart

#

im going to leave the soak tests running for 30 minutes

nova fiber May 22, 2025, 12:41 AM

#

ok there is still a bug it is just damn near impossible to reproduce

nova fiber May 22, 2025, 2:30 AM

#

ok rcu is sound, rcu shared ptr is not

#

really not sure how to make my shared pointer totally kosher

#

back to digging through https://github.com/cmuparlay/concurrent_deferred_rc/tree/master

nova fiber May 23, 2025, 1:39 AM

#

now im paranoid damnit

#

more rcu soak testing

#

i am so glad i bought the giant server cpu

#

196 cpu hours per hour is great for fuzzing and soak tests

prisma stirrup May 23, 2025, 1:42 AM

#

Can you implement snapshots in your test framework? You could easily then create a snapshot that lets you repeatedly reach the problem quicker

calm shell May 23, 2025, 1:44 AM

#

nova fiber more rcu soak testing

youre mormon?

nova fiber May 23, 2025, 1:46 AM

#

prisma stirrup Can you implement snapshots in your test framework? You could easily then create...

my test framework is just #include <cassert> for these soak tests, i usually use gtest but it doesnt like being run in parallel

prisma stirrup May 23, 2025, 1:50 AM

#

I think I misremembering, you're running the tests as a user mode program under your os which runs under qemu?

nova fiber May 23, 2025, 2:07 AM

#

the tests are just run in usermode on a linux host

#

well these ones are

#

ah i think i might have tracked it down

#

when taking nested rcu guards the generation was still allowed to change

nova fiber May 23, 2025, 3:10 AM

#

yeah that was it

nova fiber May 23, 2025, 6:17 PM

#

nova fiber May 23, 2025, 11:23 PM

#

im starting to think my rcu shared pointer is just cursed

#

i think for now im going to not use it

nova fiber May 24, 2025, 2:16 PM

#

or maybe this is a good excuse to implement hazard pointers

#

although i still want to use rcu for the fs at least

nova fiber May 24, 2025, 6:16 PM

#

some possible progress

nova fiber May 24, 2025, 7:55 PM

#

ok i think this is getting somewhere

nova fiber May 25, 2025, 12:14 AM

#

God i really hope

#

This is such a pain to test

nova fiber May 25, 2025, 3:46 AM

#

cautious optimism

nova fiber May 25, 2025, 4:22 PM

#

slowly the test cases expand

#

this is really ass but still probably faster than learning how to use SPIN and write a promela model for this

urban schooner May 25, 2025, 5:03 PM

#

What's a soak test?

calm shell May 25, 2025, 5:07 PM

#

Mormon shit don't worry about it

trim owl May 25, 2025, 5:07 PM

#

lmfao

urban schooner May 25, 2025, 5:07 PM

#

Also, which tools do you use for testing? Do you test kernel code in userspace (without emulators)?

urban schooner May 25, 2025, 5:08 PM

#

calm shell Mormon shit don't worry about it

Do you pass it

calm shell May 25, 2025, 5:08 PM

#

I'm not mormon

#

That's also not an appropriate question.

urban schooner May 25, 2025, 5:09 PM

#

I don't even know what it entails how can I know whether it is

calm shell May 25, 2025, 5:10 PM

#

Google says soak test is what normal people would call a stress test

trim owl May 25, 2025, 5:12 PM

#

urban schooner I don't even know what it entails how can I know whether it is

computer google mormon soaking

urban schooner May 25, 2025, 5:16 PM

#

trim owl computer google mormon soaking

I'm not prepared to see that

nova fiber May 25, 2025, 5:51 PM

#

urban schooner What's a soak test?

running the same test in a loop for a long time

#

i havent found any reliable way of reproducing bugs in my atomic code beyond this

#

i call them soak tests because i usually go take a piss while they run

#

halfmemeright

olive musk May 25, 2025, 10:52 PM

#

nova fiber slowly the test cases expand

your testing infrastructure looks really cool

#

I will probably take a look at it eventually and do something similar (albeit smaller in scope), though I'll do it in C

#

you could probs make repo out of your x86 simulation thingy too

nova fiber May 26, 2025, 1:47 AM

#

now that the shared pointer fiasco is over with time for a new scheduler

nova fiber May 26, 2025, 10:16 PM

#

olive musk your testing infrastructure looks really cool

thank you, i put alot of effort into the testing part

#

i did think of making the x86 simulator a seperate project but i dont think its really ready for use yet

nova fiber May 26, 2025, 11:10 PM

#

slightly gnarly but i can test my scheduler now

#

posix signals are so great if you want to do this one really specific thing and in all other cases they're really painful lol

nova fiber May 29, 2025, 12:07 AM

#

ough

nova fiber May 29, 2025, 10:48 PM

#

latest linux kernel update broke the behaviour of mprotect inside signal handlers

#

sick

#

now my x86 emulation doesnt work

urban schooner May 29, 2025, 10:52 PM

#

nova fiber latest linux kernel update broke the behaviour of `mprotect` inside signal handl...

How?

nova fiber May 29, 2025, 10:53 PM

#

urban schooner How?

changing the protection of the memory to RW, then writing to it, then changing it back to RO now always reads back 0xFFFFFFFF or 0x00000000

#

rather than what was written to the memory

urban schooner May 29, 2025, 10:53 PM

#

Huh

#

That seems unlikely

#

Or its a kernel bug

nova fiber May 29, 2025, 10:54 PM

#

its only an issue inside signal handlers when ptrace is active afaict

urban schooner May 29, 2025, 10:54 PM

#

Let them know on the mailing list

nova fiber May 29, 2025, 10:55 PM

#

i'll see if i can make a minimal reproducer

urban schooner May 29, 2025, 10:55 PM

#

Yeah

#

That seems like a serious bug

nova fiber May 29, 2025, 11:24 PM

#

it would seem canonical just decided to be retarded actually

#

setting it to 0 fixes the failing tests

urban schooner May 29, 2025, 11:26 PM

#

What does that do

nova fiber May 29, 2025, 11:26 PM

#

setting it to 1 disables ptrace for everything unless it opts in

brave cape May 29, 2025, 11:26 PM

#

urban schooner What does that do

it prints "Yama: becoming mindful." in kmesg

#

~~and that's about it~~

urban schooner May 29, 2025, 11:27 PM

#

Why do you use ptrace btw

nova fiber May 29, 2025, 11:27 PM

#

i need it to single step the test so it can set breakpoints in itself

#

the child process manipulates the parents debug registers and listens for SIGTRAP to inspect machine state and emulate priviliged instructions

urban schooner May 29, 2025, 11:28 PM

#

So it was failing with no errors?

nova fiber May 29, 2025, 11:28 PM

#

it was never updating the memory protection because the debug callback wasnt invoked

#

why it wasnt then exploding because of nested segfaults im not sure

urban schooner May 29, 2025, 11:29 PM

#

Interesting

urban schooner May 29, 2025, 11:29 PM

#

brave cape it prints "Yama: becoming mindful." in kmesg

Always wondered wtf that meant

urban schooner May 29, 2025, 11:36 PM

#

nova fiber setting it to 1 disables ptrace for everything unless it opts in

You should probably just do prctl(PR_SET_PTRACER, PR_SET_PTRACER_ANY)

#

In the code you wanna ptrace

nova fiber May 29, 2025, 11:37 PM

#

oh neat

#

thanks

urban schooner May 29, 2025, 11:38 PM

#

Found it here https://www.kernel.org/doc/html/v4.15/admin-guide/LSM/Yama.html

#

4.15 but whatever

nova fiber May 31, 2025, 2:06 AM

#

btree time

nova fiber May 31, 2025, 2:25 AM

#

i think im going to do variable arity leaf pages

nova fiber May 31, 2025, 2:06 PM

#

devilish

umbral grotto May 31, 2025, 2:44 PM

#

nova fiber <:devilish:873726114625888316>

😭

#

polyglot C++

nova fiber Jun 1, 2025, 3:29 PM

#

nova fiber i think im going to do variable arity leaf pages

fixed arity for now until i get everything else working

#

from how much everyone hypes up btrees as a hard to implement thing i was expecting alot more complexity ngl

nova fiber Jun 2, 2025, 11:35 PM

#

/home/elliothb/github/bezos/sources/kernel/include/std/container/btree.hpp:240:25: error: no matching function for call to 'swap'
  240 |                         std::swap(value(mCount - 1), entry.value);
      |                         ^~~~~~~~~
/home/elliothb/github/bezos/install/llvm/include/c++/v1/any:509:35: note: candidate function not viable: no known conversion from 'int' to 'any &' for 1st argument
``` thats a new one

#

any& it would appear clang just gave up

trim owl Jun 2, 2025, 11:40 PM

#

std::any 💀

nova fiber Jun 2, 2025, 11:40 PM

#

oh

#

bruh

#

the lack of std:: threw me

#

https://tenor.com/view/krill-gif-2620664710855382877

Tenor

trim owl Jun 2, 2025, 11:41 PM

#

why the henk are you using std::any

nova fiber Jun 2, 2025, 11:41 PM

#

im not

#

i guess i include something which transitively includes it

nova fiber Jun 4, 2025, 1:26 AM

#

spent 40% of my programs runtime executing if (i > count) panic(); award

#

actually nearly 99% of my programs runtime is just spent running validate()

#

i might be a little retarded

prisma stirrup Jun 4, 2025, 3:33 AM

#

Easy x10 speedup

small stag Jun 4, 2025, 9:34 AM

#

nova fiber actually nearly 99% of my programs runtime is just spent running `validate()`

how do you do this?

nova fiber Jun 4, 2025, 10:52 PM

#

small stag how do you do this?

flamegraph and perf

small stag Jun 5, 2025, 9:02 AM

#

nova fiber flamegraph and perf

but can you debug the kernel directly?

#

maybe via gdb?

nova fiber Jun 5, 2025, 10:34 AM

#

Yeah i debug with gdb in qemu

#

This is just peofiling code running on the linux host

nova fiber Jun 5, 2025, 11:29 AM

#

Honestly not too sure how to go about profiling the kernel

prisma stirrup Jun 5, 2025, 11:31 AM

#

Careful of profiling your kernel under qemu, while kvm would make it much more reliable than tcg it might still be misleading compared to actual hw

nova fiber Jun 7, 2025, 3:37 AM

#

i dont have any plans on profiling the kernel anytime soon ngl

#

performance hasnt been an issue at all

nova fiber Jun 7, 2025, 4:04 AM

#

i think the hardest part of testing a btree is just how much data it takes to actually fill up a tree enough for it to do interesting things

#

10 billion keys and its only got 4 leaves of depth

brave cape Jun 7, 2025, 10:38 AM

#

well you could decrease the fanout of the tree for your tests. if the tree with 10 billion keys is 4 levels deep, that means you have like 100 or 300 or something sized nodes, which is a lot. if the tree works for 10 or so, it probably also works for 100

nova fiber Jun 7, 2025, 1:21 PM

#

i now realize i can just use struct alignas(128) Key { int key; }; as a key rather than a plain int lol

nova fiber Jun 7, 2025, 1:24 PM

#

brave cape well you could decrease the fanout of the tree for your tests. if the tree with...

yeah i size my nodes based on how many key value pairs i can fit into a single node while keeping it under 0x1000 bytes large

nova fiber Jun 9, 2025, 11:53 AM

#

Insert, find, and iterate work now

#

Delete seems tricky

nova fiber Jun 10, 2025, 1:16 AM

#

swing is peak ui design

#

i must get java working in bezos

#

that was the original goal

nova fiber Jun 10, 2025, 2:50 AM

#

man deleting from btrees is way harder than insertion lol

#

rebalancing leaf nodes is a hassle

nova fiber Jun 11, 2025, 1:22 AM

#

turns out putting key value pairs in internal nodes rather than just the min or max key value makes things harder

#

i will not do that now

nova fiber Jun 14, 2025, 7:11 PM

#

nevermind the alternative was even harder

#

god this tree is a pain in the ass to get right

nova fiber Jun 14, 2025, 8:19 PM

#

on the bright side recursive lambdas are really nice

#

size_t countElements() const noexcept {
            size_t count = 0;

            auto countNode = [&](this auto&& self, const LeafNode *node) {
                count += node->count();
                if (!node->isLeaf()) {
                    const InternalNode *internal = static_cast<const InternalNode*>(node);
                    for (size_t i = 0; i < internal->count() + 1; i++) {
                        self(internal->getLeaf(i));
                    }
                }
            };

            countNode(mRootNode);
            return count;
        }

#

very shrimple

#

good feature i approve

trim owl Jun 14, 2025, 8:19 PM

#

gobless

#

although passing the lambda as an argument to itself is also simple enough

nova fiber Jun 14, 2025, 8:20 PM

#

that doesnt work if you have captures though does it?

trim owl Jun 14, 2025, 8:20 PM

#

why not, just pass the lambda by ref

nova fiber Jun 14, 2025, 8:21 PM

#

iirc it would make at least clang and gcc give up because they couldnt figure out the type of the operator()

trim owl Jun 14, 2025, 8:21 PM

#

i haven't ran into that

#

i had some lambdas that took themselves as an arg and captured [&] in a recent algo & ds class project

#

and it built just fine with c++17

nova fiber Jun 14, 2025, 8:22 PM

#

huh maybe i'm just skill issued

#

i guess im smoking crack

#

anyway back to my fuckass btree that refuses to work or be simple

nova fiber Jun 15, 2025, 2:24 AM

#

shcokingly this works

#

current implementation leaves a ton of empty or nearly empty nodes but oh well :^)

nova fiber Jun 15, 2025, 9:41 PM

#

java build systems are all as awful as i remember

#

really nasty stuff

#

anyway merging leaf nodes seems to work

nova fiber Jun 16, 2025, 1:01 AM

#

can now rebalance and merge leaf nodes

#

next is internal nodes i think

#

then finally being able to shrink the depth of the tree

nova fiber Jun 18, 2025, 3:22 AM

#

swing is the perfect retained mode gui library

#

less than 30 minutes to have something simple working

#

and i didnt want to blow my head smoove off the entire time so its already better than every js library ever written

#

i cant belive im saying this but maybe java applets werent so bad

#

also wtf why are the public amazon apis not turboass to work with

#

all the internal ones are so verbose i want to die everytime i use them

#

oh yeah osdev channel my bad

#

got btree stats working

umbral grotto Jun 18, 2025, 6:59 AM

#

nova fiber swing is the perfect retained mode gui library

what's retained mode

sour geyser Jun 18, 2025, 7:10 AM

#

Retained, as opposed to immediate mode

#

You set up state to describe what and when to render and manipulate that

#

Rather than redrawing everything all the time

#

You'd be familiar with the idea, if not the name

umbral grotto Jun 18, 2025, 7:16 AM

#

i see

nova fiber Jun 18, 2025, 12:37 PM

#

So close to being done the btree

#

Well the functionality bit

#

I still need to make it oom resilient

#

And then add bulk updates to it as well

#

And alot more testing and probably performance tuning is needed as well

tropic berry Jun 20, 2025, 11:46 PM

#

@nova fiber you alive?

#

please try the latest commit of Limine on your cursed laptop

#

see if it works

nova fiber Jun 20, 2025, 11:47 PM

#

I will give it a go this weekend

tropic berry Jun 20, 2025, 11:47 PM

#

it's saturday for me

nova fiber Jun 20, 2025, 11:47 PM

#

https://tenor.com/view/seal-disappointed-seal-crossing-arms-seal-annoyed-seal-shaking-head-seal-is-done-gif-16690635060382089112

Tenor

tropic berry Jun 20, 2025, 11:47 PM

#

i am fairly confident it is fixed

nova fiber Jun 20, 2025, 11:49 PM

#

by latest commit do you mean to trunk or to 9.x

#

since the history has diverged a bit

tropic berry Jun 21, 2025, 12:09 AM

#

both

urban schooner Jun 21, 2025, 9:31 AM

#

tropic berry i am fairly confident it is fixed

what have you changed

tropic berry Jun 21, 2025, 3:40 PM

#

urban schooner what have you changed

        - PMM: Mark EfiLoader{Code,Data} regions as bootloader reclaimable
         rather than reserved memory, as for certain protocols, like the
          Limine boot protocol, reserved memory is unmapped at runtime, while
          these regions may contain hot data that is still needed, like Limine
          bootloader memory stacks.```

urban schooner Jun 21, 2025, 3:41 PM

#

tropic berry ``` - PMM: Mark EfiLoader{Code,Data} regions as bootloader reclaimable ...

How did it not crash prior to this?

tropic berry Jun 21, 2025, 3:41 PM

#

i am honestly not sure

#

well

#

this was a regression introduced by the new base revisions of the Limine protocol that actually unmap reserved memory

#

it was not an issue before then, obviously

#

as to why it worked afterwards, i'd say probably most firmwares do not put the initial stacks in those regions?

urban schooner Jun 21, 2025, 3:43 PM

#

Hmm

tropic berry Jun 21, 2025, 3:43 PM

#

either that or some caching shenenigans

urban schooner Jun 21, 2025, 3:43 PM

#

Interesting

tropic berry Jun 21, 2025, 3:43 PM

#

tropic berry either that or some caching shenenigans

though i am not sure how the caching shenenigans are possible at all

urban schooner Jun 21, 2025, 3:44 PM

#

BTW apparently mapping high reserved memory as WB if its not covered by MTRRs can cause MCEs

#

On amd at least

tropic berry Jun 21, 2025, 3:44 PM

#

well the new revisions do not map any reserved region, so i guess that is fine

urban schooner Jun 21, 2025, 3:44 PM

#

Yeah as long as you only map usable ram

tropic berry Jun 21, 2025, 3:44 PM

#

though that's weird

#

why would the motherboard care what the CPU maps stuff as, if it is not accessed?

urban schooner Jun 21, 2025, 3:45 PM

#

Yeah apparently the CPU does some optimizations in the background and implicitly tries to access that as writeback

#

Which crashes

tropic berry Jun 21, 2025, 3:45 PM

#

that's insane

#

what the fuck

urban schooner Jun 21, 2025, 3:45 PM

#

Yeah

tropic berry Jun 21, 2025, 3:45 PM

#

what motherboard/CPU reproduces the behaviour?

urban schooner Jun 21, 2025, 3:45 PM

#

Linux had to add some workarounds for that

urban schooner Jun 21, 2025, 3:46 PM

#

tropic berry what motherboard/CPU reproduces the behaviour?

I can send u the commit if u want to dig deeper, I havent tho

tropic berry Jun 21, 2025, 3:46 PM

#

i mean sure, ty

urban schooner Jun 21, 2025, 3:46 PM

#

Basically they had to change the logic for how they build their HHDM

#

To carve out usable ram and only map that

tropic berry Jun 21, 2025, 3:47 PM

#

yeah so basically what revisions 2/3 of the lbp already moved to

urban schooner Jun 21, 2025, 3:47 PM

#

Ye

tropic berry Jun 21, 2025, 3:47 PM

#

insane, i moved to that just because i thought it was more sensible

#

and would avoid running out of RAM potentially if there were massive reserved regions

#

but like

#

i didn't know about this, that's convenient

urban schooner Jun 21, 2025, 3:48 PM

#

#1217009725711847465 message

tropic berry Jun 21, 2025, 3:50 PM

#

how did you even run into this

urban schooner Jun 21, 2025, 3:50 PM

#

Just studying how Linux builds their direct map

#

Looking at what abstractions they have etc

tropic berry Jun 21, 2025, 3:51 PM

#

i see

#

well ty for letting me know, i will store this in my brain under the "AMD bullshit" category, along with the fact that you need to use rax to access ECAM space

urban schooner Jun 21, 2025, 3:51 PM

#

Ill have to fix hyper to not do that as well

#

Yeah lol

#

So much bs from amd

olive musk Jun 21, 2025, 3:52 PM

#

I'll have to fix my kernel not to do that too

#

So you ensure you just map usable memory?

urban schooner Jun 21, 2025, 3:52 PM

#

Well for pages that aren't usable memory u map them as uncached

olive musk Jun 21, 2025, 3:52 PM

#

I wonder how the guy even found where the bug came from lol

urban schooner Jun 21, 2025, 3:52 PM

#

Or don't map at all

urban schooner Jun 21, 2025, 3:53 PM

#

olive musk I wonder how the guy even found where the bug came from lol

Yeah no idea

olive musk Jun 21, 2025, 3:53 PM

#

So instead of blindly mapping the first 4 gib (or higher if you have more memory) I should just map usable entries

urban schooner Jun 21, 2025, 3:53 PM

#

First 4g are covered by mtrr so u can blindly map

#

But above that yes

tropic berry Jun 21, 2025, 8:26 PM

#

@nova fiber it is the weekend now

nova fiber Jun 21, 2025, 8:30 PM

#

aye, i built the limine images i just need to monkey patch my kernel build again

nova fiber Jun 21, 2025, 8:47 PM

#

yup works now

#

my kernel immediately explodes on this laptop but limine is fine

#

@tropic berry

tropic berry Jun 21, 2025, 9:01 PM

#

yay ty

nova fiber Jun 22, 2025, 12:54 AM

#

btree finally works

#

i dont think that was worse than the tlsf allocator in terms of difficulty but that was definetly more finnicky

#

so many edge cases

#

fun exercise though, but i think i'll hold off on implementing a b+tree

nova fiber Jun 22, 2025, 1:16 PM

#

i've been robbed

#

thank god i setup cost alarms

#

nova fiber Jun 22, 2025, 5:32 PM

#

man wtf is going on at java conferences

trim owl Jun 22, 2025, 5:36 PM

#

allegro-sponsored hentai rental store in warsaw

brave cape Jun 22, 2025, 5:38 PM

#

nova fiber man wtf is going on at java conferences

😭 they use swedish krona (SEK) as currency

zealous mirage Jun 22, 2025, 6:37 PM

#

nova fiber man wtf is going on at java conferences

ruby conferences had them beat

#

there was a presentation at one titled, and i quote exactly, "CouchDB: Perform like a Pr0nstar", complete with a picture of a nude woman on each slide

#

this was what fired off the entire CoC movement in software

nova fiber Jun 22, 2025, 6:40 PM

#

bruh

nova fiber Jun 25, 2025, 1:53 AM

#

fixed yet another bug in the btree

#

woe 5 million edge cases be upon ye

nova fiber Jun 25, 2025, 3:53 AM

#

i think i've beaten all the edge cases out of this damn tree

#

I dont trust the implementation so i think more tests are in order but if it does work then i have a btree thats resistent to oom

#

which i think is the last data structure i need to replace abseil and make my entire kernel oom resistent

nova fiber Jun 25, 2025, 4:17 PM

#

nova fiber Jun 26, 2025, 4:25 AM

#

now have some fuzz testing and stress testing for the btree and it seems to still work

#

performance is meh but i know a few things i did wrong that are easy to fix

nova fiber Jun 26, 2025, 12:48 PM

#

looking at test coverage its not quite 100%

#

theres a few branches that are never taken

#

slightly worrying

#

A couple are because I dont have any tests for oom cases which is fine

#

one is that i never test the branch of splitting the root node when its an internal node

#

which is more concerning

#

anyway time for employment

nova fiber Jun 27, 2025, 2:52 AM

#

i do not like being oncall

#

anyway adding custom allocator support

#

oh and custom comparator support

urban schooner Jun 27, 2025, 7:35 AM

#

nova fiber i do not like being oncall

same

nova fiber Jun 27, 2025, 12:27 PM

#

Custom allocators work now, and I also have test coverage for the oom cases

#

Just comparators left

#

The end is in sight for this damn btree

#

Oh I guess I'll need to implement another one for fs related stuff

calm shell Jun 27, 2025, 12:32 PM

#

nova fiber Oh I guess I'll need to implement another one for fs related stuff

see this guy?

nova fiber Jun 27, 2025, 12:34 PM

#

Inb4 he spent his entire career writing btrees

calm shell Jun 27, 2025, 12:34 PM

#

that guy (gordon letwin) implemented a b+tree for the hpfs driver for os/2 in 16-bit x86 assembly and it was so large that it needed to be split into different segments which would be explicitly hot-loaded in and out (potentially incurring segment swapping to disk), while doing an efficient b+tree rebalance on disk

#

in like 1985

#

so u have no excuse.

nova fiber Jun 27, 2025, 12:34 PM

#

Oh man

#

I haven't even bothered to look at the code size of my btree lol

calm shell Jun 27, 2025, 12:35 PM

#

and it worked perfectly. no bugs ever found

olive musk Jun 27, 2025, 12:35 PM

#

Ok but he's never written a Cthulhu compiler has he

nova fiber Jun 27, 2025, 12:36 PM

#

I'm hoping to at least manage the bug free bit with the amount of testing I'm doing

#

It helps that I can run 3 cpu hours of testing every minute on my machine meme

calm shell Jun 27, 2025, 12:37 PM

#

also i just found this blog post by googling gordon letwin that im 90% sure is completely chatgpt generated https://medium.com/@jason.poulopoulos/a-rebooting-perspective-from-july-22-ea8bf92cef19

nova fiber Jun 27, 2025, 12:39 PM

#

I should setup some real™ fuzzing with afl for some of my code next probably. I imagine just using rng isn't catching everything

olive musk Jun 27, 2025, 12:39 PM

#

Do you have kernel mode tests

#

Like kunit

olive musk Jun 27, 2025, 12:40 PM

#

calm shell also i just found this blog post by googling gordon letwin that im 90% sure is ...

This is 100% chatgpt

#

#

Lmao

calm shell Jun 27, 2025, 12:41 PM

#

you can tell by the like sassy buzzfeed writing style

#

and the overuse of analogies

#

that dont quite fit

olive musk Jun 27, 2025, 12:42 PM

#

No human would describe NTFS as a digital fort knox

olive musk Jun 27, 2025, 12:42 PM

#

calm shell and the overuse of analogies

yeah this is what sells it the most

calm shell Jun 27, 2025, 12:42 PM

#

also the emdashes

olive musk Jun 27, 2025, 12:43 PM

#

Ah look at the author's description

#

"sent from my neural network"

#

Idk what that means exactly but even he admits this is AI

nova fiber Jun 27, 2025, 12:49 PM

#

olive musk Do you have kernel mode tests

I've been a bit lacking in that department, I had a couple but they weren't very good so I canned them

#

I think I'll try writing some new ones soon ish

#

My only tests like that right now are a script that launches every emulator I have with a kernel image

#

I should try to automate network booting again on some of my machines would be cool having a rack of actual test hardware

calm shell Jun 27, 2025, 12:52 PM

#

will it be rock solid enough to forkbomb indefinitely and keep enough sanity for the user to recover

#

linux cant do that.

nova fiber Jun 27, 2025, 12:53 PM

#

How would one go about doing that

calm shell Jun 27, 2025, 12:53 PM

#

just do sane things when you run out of resources

nova fiber Jun 27, 2025, 12:54 PM

#

How would you handle there's a bazillion processes sanely

calm shell Jun 27, 2025, 12:55 PM

#

dont crash

nova fiber Jun 27, 2025, 12:55 PM

#

Well yeah that's like the baseline

calm shell Jun 27, 2025, 12:55 PM

#

linux crashes

nova fiber Jun 27, 2025, 12:55 PM

#

Not sure how you'd make it remain responsive though

calm shell Jun 27, 2025, 12:55 PM

#

thread priorities and pre-allocating anything needed for recovery

nova fiber Jun 27, 2025, 12:56 PM

#

So marking interactive processes as very high priority

calm shell Jun 27, 2025, 12:56 PM

#

something like that

nova fiber Jun 27, 2025, 12:56 PM

#

Hmm fair enough

calm shell Jun 27, 2025, 12:57 PM

#

calm shell linux crashes

VMS does not!

nova fiber Jun 27, 2025, 12:57 PM

#

I was expecting arcane scheduling algorithms and heuristic honestly

nova fiber Jun 28, 2025, 3:32 PM

#

i now have actual fuzz targets for the btree

#

will run them for a few hours to see if anything crashes

nova fiber Jun 28, 2025, 5:26 PM

#

ok 32 cpu hours of fuzzing and no bugs found

#

I think thats good enough for me

olive musk Jun 28, 2025, 6:31 PM

#

nova fiber I think thats good enough for me

it's not

#

you need to run them for a year

#

at least

nova fiber Jun 29, 2025, 1:52 AM

#

hmm the abseil btree scales better than mine at large element counts

#

reducing the internal node size gets me closer to their performance at large element counts but its worse at smaller counts

#

ah right i remember my merging of nodes is stupidly badly implemented

#

n^2 complexity node merging trl

olive musk Jun 29, 2025, 2:27 AM

#

nova fiber n^2 complexity node merging <:trl:829316641191886888>

unit testing man whats the best test framework in your opinion

#

I like doctest but idk if I should use gtest instead

nova fiber Jun 29, 2025, 2:27 AM

#

gtest is pretty good in my experience

olive musk Jun 29, 2025, 2:27 AM

#

and for fuzzing do you use google's fuzztest?

nova fiber Jun 29, 2025, 2:28 AM

#

i just write llvm fuzz targets currently

olive musk Jun 29, 2025, 2:28 AM

#

doctest is catch2 but doesnt take ages to compile basically

nova fiber Jun 29, 2025, 2:28 AM

#

google fuzztest is a bit hard to build with meson

olive musk Jun 29, 2025, 2:28 AM

#

ah

nova fiber Jun 29, 2025, 2:28 AM

#

catch2 is really scuffed

#

dont like that library

olive musk Jun 29, 2025, 2:28 AM

#

why?

nova fiber Jun 29, 2025, 2:28 AM

#

it does all kinds of fucky stuff for no good reason

#

redirects stdout and stderr and applies broken formatting rules to it, installs exception handlers on windows which breaks alot of stuff

#

i think it also fucks with some signal handlers

olive musk Jun 29, 2025, 2:29 AM

#

i think doctest is better

nova fiber Jun 29, 2025, 2:29 AM

#

which is just like bruh

olive musk Jun 29, 2025, 2:29 AM

#

olive musk Jun 29, 2025, 2:30 AM

#

nova fiber i just write llvm fuzz targets currently

how do you structure stuff? a tests directory with unit tests and fuzzing targets combined or do you have different files for each

nova fiber Jun 29, 2025, 2:30 AM

#

kernel
  - src
  - include
  - test
    - container
      - btree.cpp
      - btree_stress.cpp
      - btree_fuzz.cpp
``` currently

#

maybe eventually i'll have seperate folders specifically for fuzz targets

olive musk Jun 29, 2025, 2:31 AM

#

ahh that makes sense

#

I will steal this

nova fiber Jun 29, 2025, 2:31 AM

#

i also put the benchmarks in the same folder

olive musk Jun 29, 2025, 2:31 AM

#

im testing C code tho

#

should still work fine

nova fiber Jun 29, 2025, 2:31 AM

#

i mean you can have tests written in c++ for testing c code

olive musk Jun 29, 2025, 2:31 AM

#

yea

#

C tests frameworks are lacking

#

compared to C++ ones

nova fiber Jun 29, 2025, 2:35 AM

#

c doesnt really have the facilities for what makes test code nice to write

#

very hard to do automatic registration of tests

olive musk Jun 29, 2025, 2:39 AM

#

yeah

nova fiber Jun 29, 2025, 2:41 AM

#

annoyingly i think java probably has the best testing frameworks

#

junit5 is really nice to use

olive musk Jun 29, 2025, 2:45 AM

#

what the fuck

nova fiber Jun 29, 2025, 2:46 AM

#

bruh

nova fiber Jun 29, 2025, 2:35 PM

#

I think clang has shit the bed quite badly

#

im not tripping that this is valid c++ ```cpp

std::vector<int> GenerateKeys(size_t count) {
    std::vector<int> keys;
    keys.reserve(count);
    for (size_t i = 0; i < count; i++) {
        keys.push_back(int(i * 10));
    }
    return keys;
}

std::vector<int> GenerateRandomKeys(size_t count) {
    std::vector<int> keys = GenerateKeys(count);
    std::shuffle(keys.begin(), keys.end(), mt);
    return keys;
}

#

asan dies on it though

📎 message.txt

#

ok thread sanitizer is tripping on data races to llvms coverage internals

#

hm nuking the build directory fixed it partially

umbral grotto Jun 29, 2025, 4:11 PM

#

nova fiber asan dies on it though

what the hell is a container overflow

#

and how is a container overflow possible if the byte is 0 bytes within a 2044 byte region

#

also why is the region size not aligned to 8 bytes wtf

nova fiber Jun 29, 2025, 4:11 PM

#

it was a false positive

#

really not sure what caused it though

#

I find it very aggravating that the clang and llvm teams went through alot of effort to make sure sanitizers dont break abi, and then google abseil just throws that out the window and makes enabling sanitizers change abis for like half their containers

#

more reason to be rid of it i guess

stone igloo Jun 29, 2025, 4:19 PM

#

nova fiber I find it very aggravating that the clang and llvm teams went through alot of ef...

i think that makes sense tbh

#

enabling extra checks in debug mode is reasonable

nova fiber Jun 29, 2025, 5:26 PM

#

ah well i just disabled the 2 failing tests

#

will fix them some other time when i can be bothered to deal with picking apart the build graph

#

in better news my btree is now significantly faster than abseils

#

----------------------------------------------------------------------
Benchmark                            Time             CPU   Iterations
----------------------------------------------------------------------
BM_AbseilBtreeInsert/32         166697 ns       166694 ns         4321
BM_AbseilBtreeInsert/64         309305 ns       309304 ns         2105
BM_AbseilBtreeInsert/512       3374607 ns      3374569 ns          206
BM_AbseilBtreeInsert/4096     31639941 ns     31639079 ns           22
BM_AbseilBtreeInsert/32768   282632297 ns    282615806 ns            2
BM_AbseilBtreeInsert/131072 1200292838 ns   1200249039 ns            1
BM_BezosBtreeInsert/32            4492 ns         4492 ns       156003
BM_BezosBtreeInsert/64           13876 ns        13875 ns        50178
BM_BezosBtreeInsert/512         653867 ns       653844 ns         1071
BM_BezosBtreeInsert/4096       7534689 ns      7533914 ns           93
BM_BezosBtreeInsert/32768     68250443 ns     68250797 ns           10
BM_BezosBtreeInsert/131072   356750578 ns    356751991 ns            2
``` pretty happy with this

olive musk Jun 29, 2025, 5:28 PM

#

did you enable optimizations?

#

at some point I thought I was beating abseil's hashmap

#

but optimizations werent enabled meme

nova fiber Jun 29, 2025, 5:29 PM

#

fair point

olive musk Jun 29, 2025, 5:29 PM

#

because abseil handles optimizations very well usually and is significantly faster

nova fiber Jun 29, 2025, 5:30 PM

#

----------------------------------------------------------------------
Benchmark                            Time             CPU   Iterations
----------------------------------------------------------------------
BM_AbseilBtreeInsert/32           1016 ns         1016 ns       704989
BM_AbseilBtreeInsert/64           2235 ns         2235 ns       313278
BM_AbseilBtreeInsert/512         24204 ns        24203 ns        29537
BM_AbseilBtreeInsert/4096       370072 ns       370073 ns         1962
BM_AbseilBtreeInsert/32768     3479640 ns      3479541 ns          202
BM_AbseilBtreeInsert/131072   15598496 ns     15598276 ns           43
BM_BezosBtreeInsert/32             348 ns          348 ns      2062867
BM_BezosBtreeInsert/64            1114 ns         1114 ns       618366
BM_BezosBtreeInsert/512          69912 ns        69913 ns         9617
BM_BezosBtreeInsert/4096        821538 ns       821521 ns          843
BM_BezosBtreeInsert/32768      7343610 ns      7343648 ns           93
BM_BezosBtreeInsert/131072    38884775 ns     38884592 ns           18
----------------------------------- stderr -----------------------------------
``` hm i still do better at smaller element count but my node splitting is a bit inefficient

olive musk Jun 29, 2025, 5:31 PM

#

yeah they tend to optimize larger sets I guess

nova fiber Jun 29, 2025, 5:32 PM

#

i think its just because my rebalancing and splitting is implemented in a really stupid way lol

olive musk Jun 29, 2025, 5:32 PM

#

but still that is very good considering most times your kernel wont have that much optimizations enabled and your thing is freestanding

stone igloo Jun 29, 2025, 6:10 PM

#

nova fiber ``` ---------------------------------------------------------------------- Bench...

what about the rust btree?

nova fiber Jun 29, 2025, 10:13 PM

#

I havent a clue, is the rust btree any good?

nova fiber Jul 1, 2025, 7:35 PM

#

anyway now that the btree works back to scheduling

#

i have some actual unit tests for this one

nova fiber Jul 1, 2025, 10:57 PM

#

spent 2 hours tracking down a bug in the scheduler and it was actually a bug in my test code

#

nova fiber Jul 1, 2025, 11:34 PM

#

so my scheduler works fine but my tests are flakey because the linux scheduler will sometimes decide to just not schedule the test thread for long enough

#

very annoying

#

ok finally got the tests not flakey i think

#

This little python script has been very handy https://github.com/google/gtest-parallel

GitHub

GitHub - google/gtest-parallel: Run Google Test suites in parallel.

Run Google Test suites in parallel. Contribute to google/gtest-parallel development by creating an account on GitHub.

nova fiber Jul 2, 2025, 2:59 AM

#

fun leenox thing i have discovered

#

there appears to be a quite low upper limit on how many signals you can send per second that seems to be tied to each hardware thread

#

which i imagine in 99.9% of code is not an issue

#

but my entire test infrastructure depends on being able to yeet around signals

#

halfmemeright at least it helps me discover race conditions

#

actually this limit might be global

#

does linux take some big lock somewhere when sending a signal

#

if i run the same test on 64 threads it takes about 900ms per run, but if i run the same test on 128 threads it takes up to 2000ms

calm shell Jul 2, 2025, 3:04 AM

#

nova fiber does linux take some big lock somewhere when sending a signal

i sure hope not

#

there are terrifying implications about the existence of some evil flag on some evil syscall somewhere if they were forced to do a big lock around signals

nova fiber Jul 2, 2025, 3:07 AM

#

in my case these are signals sent with pthread_sigqueue so maybe thats a special case or something

#

surely signals that get routed back to the current process or thread dont have this behaviour

#

i hope

nova fiber Jul 3, 2025, 12:49 AM

#

[----------] Global test environment tear-down
[==========] 4 tests from 1 test suite ran. (1518 ms total)
[  PASSED  ] 4 tests.
----------------------------------- stderr -----------------------------------
==494247==WARNING: ASan is ignoring requested __asan_handle_no_return: stack type: default top: 0x755801efee80; bottom 0x77f8042e3000; size: 0xfffffd5ffdc1be80 (-2886255657344)
False positive error reports may follow
For details see https://github.com/google/sanitizers/issues/189
``` never seen this before

nova fiber Jul 4, 2025, 11:27 PM

#

made my btree a little more correct™ in respect to move semantics

#

so i should be able to put unique_ptrs into it

nova fiber Jul 5, 2025, 12:22 AM

#

----------------------------------------------------------------------
Benchmark                            Time             CPU   Iterations
----------------------------------------------------------------------
BM_AbseilBtreeInsert/32           1004 ns         1004 ns       702164
BM_AbseilBtreeInsert/64           2237 ns         2237 ns       309835
BM_AbseilBtreeInsert/512         23656 ns        23656 ns        29687
BM_AbseilBtreeInsert/4096       366434 ns       366425 ns         1937
BM_AbseilBtreeInsert/32768     3494527 ns      3494471 ns          201
BM_AbseilBtreeInsert/131072   15795159 ns     15787811 ns           44
BM_BezosBtreeInsert/32             397 ns          397 ns      1741940
BM_BezosBtreeInsert/64            1089 ns         1089 ns       649221
BM_BezosBtreeInsert/512          44395 ns        44395 ns        16188
BM_BezosBtreeInsert/4096        535292 ns       535283 ns         1274
BM_BezosBtreeInsert/32768      5008254 ns      5008275 ns          139
BM_BezosBtreeInsert/131072    22207820 ns     22206906 ns           32
BM_AbseilBtreeFind/32              220 ns          220 ns      3224565
BM_AbseilBtreeFind/64              538 ns          538 ns      1286350
BM_AbseilBtreeFind/512            6774 ns         6774 ns       106461
BM_AbseilBtreeFind/4096         107758 ns       107347 ns         6368
BM_AbseilBtreeFind/32768       1663392 ns      1663395 ns          422
BM_AbseilBtreeFind/131072      8411123 ns      8411073 ns           83
BM_BezosBtreeFind/32               214 ns          212 ns      3288641
BM_BezosBtreeFind/64               507 ns          507 ns      1382288
BM_BezosBtreeFind/512             6622 ns         6622 ns       105640
BM_BezosBtreeFind/4096           62806 ns        62806 ns        11134
BM_BezosBtreeFind/32768        1549433 ns      1549365 ns          447
BM_BezosBtreeFind/131072      13093260 ns     13092940 ns           54
``` inching closer to abseils btree

nova fiber Jul 5, 2025, 1:11 AM

#

BM_AbseilBtreeFind/32              210 ns          210 ns      3373836
BM_AbseilBtreeFind/64              522 ns          522 ns      1328218
BM_AbseilBtreeFind/512            6569 ns         6569 ns       106476
BM_AbseilBtreeFind/4096         101972 ns       101969 ns         6651
BM_AbseilBtreeFind/32768       1673233 ns      1673149 ns          419
BM_AbseilBtreeFind/131072      8359888 ns      8359453 ns           84
BM_BezosBtreeFind/32               212 ns          211 ns      3326127
BM_BezosBtreeFind/64               507 ns          507 ns      1383173
BM_BezosBtreeFind/512             6912 ns         6912 ns       100871
BM_BezosBtreeFind/4096           81907 ns        81906 ns         8568
BM_BezosBtreeFind/32768        1434938 ns      1434941 ns          487
BM_BezosBtreeFind/131072       7289521 ns      7288763 ns           96
``` google eat your heart out

#

insert is still lagging behind a bit but i know why now

#

I think i might be able to beat googles insert by alot with a bit more effort

#

google doesnt use a floating node start point which i think i should be able to implement

nova fiber Jul 5, 2025, 3:18 AM

#

storing the parent index in each child node lost me about 1% performance

#

and it destroyed the debug performance

#

not doing that

nova fiber Jul 5, 2025, 3:47 AM

#

seeing as it wasnt that im not sure what abseil is doing that im not

#

oh hm maybe its the data layout

#

abseil stores pair<key, value> data[] in its nodes, i store key keys[]; value values[];

#

so i suppose it would make sense their insert is faster because the insert has better locality

#

and my find is better because it has better locality when searching

#

abseil also uses significantly smaller node sizes than i do

#

they target 256 bytes per btree node and i target 4k, so my search has a much shallower path

#

but rebalancing is going to be more expensive

#

i wonder if fiddling with the target node size could improve performance

#

the bigger the node the faster the search and the slower the insert

#

i guess that makes sense

#

----------------------------------------------------------------------
Benchmark                            Time             CPU   Iterations
----------------------------------------------------------------------
BM_AbseilBtreeInsert/32            980 ns          980 ns       718313
BM_AbseilBtreeInsert/64           2189 ns         2189 ns       323443
BM_AbseilBtreeInsert/512         22612 ns        22612 ns        31039
BM_AbseilBtreeInsert/4096       351221 ns       351223 ns         2010
BM_AbseilBtreeInsert/32768     3401683 ns      3401557 ns          207
BM_AbseilBtreeInsert/131072   15356178 ns     15355598 ns           46
BM_BezosBtreeInsert/32             370 ns          370 ns      1909469
BM_BezosBtreeInsert/64            1050 ns         1050 ns       656605
BM_BezosBtreeInsert/512          18329 ns        18329 ns        37530
BM_BezosBtreeInsert/4096        192800 ns       192799 ns         3544
BM_BezosBtreeInsert/32768      2616822 ns      2615590 ns          265
BM_BezosBtreeInsert/131072    12181829 ns     12181126 ns           58
BM_AbseilBtreeFind/32              225 ns          225 ns      3109016
BM_AbseilBtreeFind/64              558 ns          557 ns      1292646
BM_AbseilBtreeFind/512            6849 ns         6848 ns       102231
BM_AbseilBtreeFind/4096          99543 ns        99543 ns         6388
BM_AbseilBtreeFind/32768       1675751 ns      1675628 ns          412
BM_AbseilBtreeFind/131072      8414508 ns      8414289 ns           83
BM_BezosBtreeFind/32               211 ns          211 ns      3318670
BM_BezosBtreeFind/64               506 ns          506 ns      1378679
BM_BezosBtreeFind/512             7200 ns         7200 ns        97214
BM_BezosBtreeFind/4096           81420 ns        81420 ns         8649
BM_BezosBtreeFind/32768        1507127 ns      1507130 ns          461
BM_BezosBtreeFind/131072       7104118 ns      7103604 ns           99

success

#

and i will note that my node size is still 4x the google one

#

i guess doing SOA rather than AOS makes quite a difference

#

although saying that in real™ usage im going to keep the node size to either the disk block size or the isa page size

#

but good to know that my btree isnt too much of a slouch

nova fiber Jul 5, 2025, 12:13 PM

#

BM_AbseilBtreeErase/32             336 ns          336 ns      2082525
BM_AbseilBtreeErase/64             679 ns          679 ns      1018326
BM_AbseilBtreeErase/512           5383 ns         5383 ns       130322
BM_AbseilBtreeErase/4096         43505 ns        43505 ns        16270
BM_AbseilBtreeErase/32768       344294 ns       344295 ns         2014
BM_AbseilBtreeErase/131072     1416851 ns      1416857 ns          469
BM_BezosBtreeErase/32             26.7 ns         26.7 ns     26035775
BM_BezosBtreeErase/64             54.2 ns         54.2 ns     11838819
BM_BezosBtreeErase/512             437 ns          437 ns      1589267
BM_BezosBtreeErase/4096           3383 ns         3383 ns       205233
BM_BezosBtreeErase/32768         27143 ns        27142 ns        25560
BM_BezosBtreeErase/131072       110609 ns       110610 ns         5650
``` i also demolish abseil on erasing elements

nova fiber Jul 5, 2025, 12:42 PM

#

actually i was benchmarking erase a bit incorrectly

#

im a touch slower than abseil

nova fiber Jul 6, 2025, 4:55 PM

#

anyway back to actually working on the kernel

#

new scheduler is looking alot less unstable

#

will see if i can hack together some test images so i can test them a bit more thoroughly

#

signals are pretty good but emulating page tables swapping and other systems interacting with it is a bit painful still

nova fiber Jul 6, 2025, 6:56 PM

#

I have forgotten what the apic ISR is for

#

https://tenor.com/view/muscleman-dementia-my-mom-dementia-man-stupid-gif-22895145

Tenor

#

why are timer interrupts not being delived on my bsp thnk

#

Oh i think the problem is the PIT is still running, and i don't have an interrupt on the PIT IVT entry so i never send the EOI signal

#

so i then never get another interrupt because of that

#

that seems plausible

nova fiber Jul 6, 2025, 9:14 PM

#

bruh i spent like 2 hours debugging why task switching wasnt working

#

it was working the entire time

#

i forgot that my logging was async so the buffer was filling up faster than it could flush so it looked like only one task was ever beeing ran

#

https://cdn.discordapp.com/attachments/976384146664484885/1369724140818399344/clorox.gif

calm shell Jul 6, 2025, 9:16 PM

#

lol

nova fiber Jul 6, 2025, 9:17 PM

#

on the bright side i was at least able to use said logger to debug this since its entirely reentrant

#

you win some you lose some

#

and just in case i now have a test to ensure that my scheduler is somewhat fair

olive musk Jul 6, 2025, 9:24 PM

#

man is the unit test lord

#

is that in kernel mode still?

nova fiber Jul 6, 2025, 9:24 PM

#

all my scheduler tests are still in usermode

olive musk Jul 6, 2025, 9:24 PM

#

ah still very cool

nova fiber Jul 6, 2025, 9:25 PM

#

i've been working on making proper test images so i can run gtest in kernel mode but thats taking a bit

olive musk Jul 6, 2025, 9:25 PM

#

you could do something like kunit

nova fiber Jul 6, 2025, 9:26 PM

#

kunit is loadable kernel modules that poke stuff right?

olive musk Jul 6, 2025, 9:30 PM

#

I think it's basically unit tests as loadable modules yea

nova fiber Jul 6, 2025, 9:30 PM

#

at the point i have loadable modules i'll definetly look at that

olive musk Jul 6, 2025, 9:30 PM

#

you can do it without modules too

#

opt-in on compilation or something

nova fiber Jul 6, 2025, 9:31 PM

#

i mean thats basically what my test images are right now

#

they just have a different kmain function

#

but being able to run all the tests in a single vm would probably be good

#

right now i launch a qemu domain with libvert per test suite

#

i really need some way of launching the tests in every vm i've got

#

qemu is a bit lax

nova fiber Jul 9, 2025, 3:11 AM

#

im able to test my multicore scheduler but addrsan isnt able to cope

#

pain

nova fiber Jul 10, 2025, 2:35 AM

#

figured it out

#

had to send an extra interrupt to each thread

nova fiber Jul 10, 2025, 3:18 AM

#

all the llvm sanitizers remain very unhappy though

#

i guess completely nonlocal control flow and custom thread context switching doesnt agree with them

nova fiber Jul 11, 2025, 12:12 AM

#

man these scheduler tests a bit flakey no matter what i try

#

im at the mercy of the linux scheduler to actually give the tests enough of a timeslice to run within time

#

does linux have anything in the way of "please give me the next 200ms of cpu time on this core" or equivalent

#

pthread_attr_setschedpolicy seems to be round about what i want

nova fiber Jul 11, 2025, 12:40 AM

#

setting the scheduling policy seems to kinda help

#

not sure how i'd integrate sudo setcap CAP_SYS_NICE+ep into the build process sanely though lol

#

I guess as part of the build i could add some stuff to the sudoers file to allow that to be invoked specifically on the tests that need it

iron mist Jul 11, 2025, 7:10 AM

#

nova fiber does linux have anything in the way of "please give me the next 200ms of cpu tim...

sched_fifo gives you an infinite timeslice

#

so just set the scheduling policy to that for 200ms

nova fiber Jul 12, 2025, 7:44 PM

#

integrated it into the kernel and it seems to be working

nova fiber Jul 21, 2025, 12:28 PM

#

Got some basic sleeping implemented, still need to test it though

hollow gorge Jul 21, 2025, 10:39 PM

#

wut is going on here

#

ohhh you save all registers

nova fiber Jul 22, 2025, 4:57 PM

#

Yeah it's a touch silly, I should probably clean up some stuff

nova fiber Jul 24, 2025, 12:38 AM

#

got some basic tests for sleeping

#

seems to work properly

#

testing timing sensitive stuff is kinda hard

hollow gorge Jul 24, 2025, 1:08 AM

#

nova fiber testing timing sensitive stuff is kinda hard

tickless mode and RT threads make the timing sensitive stuff happier

#

make a realtime thread priority

nova fiber Jul 24, 2025, 1:09 AM

#

i mean unit testing it, actually verifying it works manually is fine

#

i dont particularly want to mark all my tests with a bunch of SUID bits to make them run properly

nova fiber Jul 24, 2025, 2:19 AM

#

slightly random but got my c++ docker client working enough to use for testing stuff

#

used testcontainers a bit on some java project and im pretty sold with the experience

#

very good idea to be able to create a docker container with a database or something in it for unit tests

nova fiber Jul 25, 2025, 3:44 AM

#

very nice

#

anyway back to OS stuff, im actually integrating the scheduler into my existing system so i hope to have a working userspace again soon

#

or at least a less unstable one

nova fiber Jul 27, 2025, 12:04 AM

#

man actually integrating the scheduler is a bit painful

#

i dont want to just shove void*s into the scheduler entry struct but i dont have any good way of getting the associated system thread from the scheduler entry

hollow gorge Jul 27, 2025, 1:44 AM

#

nova fiber i dont want to just shove void*s into the scheduler entry struct but i dont have...

huh

#

wuhduyumean

nova fiber Jul 27, 2025, 1:45 AM

#

my current scheduler holds scheduler entries, but a scheduler entry alone is not enough to reconstruct a tasks state so it can be run. i need stuff like the kernel syscall stack pointer and extra bits i don't store in the entry

#

and i cant think of any good way of getting that context from the scheduler entry that isnt either really fucky offsetof hacks or just cramming random pointers into the scheduler entry

hollow gorge Jul 27, 2025, 1:48 AM

#

nova fiber my current scheduler holds scheduler entries, but a scheduler entry alone is not...

uhhh scheduler entries?

#

so like thread queues?

#

or what

nova fiber Jul 27, 2025, 1:49 AM

#

I have a scheduler entry which contains everything the scheduler needs to know ```cpp
struct SchedulerEntry {
uint64_t mId;
std::atomic<TaskStatus> mStatus{TaskStatus::eIdle};
std::atomickm::os_instant mSleepUntil;
TaskState mState;
};

```cpp
struct Thread {
        sm::RcuWeakPtr<Process> mProcess;

        /// @brief Intrusive sheduler entry block.
        task::SchedulerEntry mSchedulerEntry;

        km::StackMapping mKernelStack;
        km::StackMapping mUserStack;
};

#Jeff BezOS