mirror of
https://github.com/subhobhai943/SUB-OS.git
synced 2026-10-25 16:52:29 +00:00
subhobhai943andClaude Opus 5
f9400f6ac4
Expands the kernel-and-TTY core with the primitives the higher layers have
been missing, plus an in-kernel harness that proves they work.
Data structures (lib/):
- rbtree.c: Linux-compatible red-black tree with parent pointers, full
insert/erase rebalancing, in-order iteration and an invariant validator.
- kfifo.c: power-of-two byte ring with free-running indices, so the wrap
path costs one mask instead of a branch per byte.
- hashtable.c: separately-chained table with FNV-1a hashing, string or
u64 keys, and rehash-on-growth at a 3/4 load factor.
Kernel subsystems:
- kernel/wait.c: wait queues and one-shot completion barriers, backed by a
static sleeper pool so a blocking path never re-enters the allocator.
- kernel/futex.c: 32-bucket futex hash with value re-check, requeue, and an
fmutex_t sleeping mutex built on the uncontended-fastpath protocol.
- kernel/rcu.c: tiny RCU with reader nesting, deferred callbacks, kfree_rcu
and rcu_assign_pointer/rcu_dereference publish barriers.
- mm/page_cache.c: write-back block page cache, 4 KB pages indexed by
(device, page), CLOCK second-chance eviction and dirty write-back.
- kernel/ktest.c: KUnit-style harness with 6 built-in suites, 21 cases and
735 assertions covering every subsystem above (all passing under QEMU).
LazyBox userland:
- coreutils.c: sort, uniq, cut, tr, rev, tac, nl, seq, diff, xxd, du,
factor, sum and truncate, reading through the VFS and handling the
zero-length synthetic nodes that procfs and sysfs expose.
- ktest, rcuinfo, futexinfo, waitinfo and pagecache diagnostics applets.
Co-Authored-By: Claude Opus 5 <[email protected]>
Claude-Session: https://claude.ai/code/session_01L5yKJT4Wo2cV3rfPrwY5MP
63 lines
2.0 KiB
C
63 lines
2.0 KiB
C
#ifndef _KERNEL_FUTEX_H
|
|
#define _KERNEL_FUTEX_H
|
|
|
|
#include <stdint.h>
|
|
#include <stddef.h>
|
|
#include <stdbool.h>
|
|
#include <kernel/wait.h>
|
|
|
|
// Fast Userspace muTEX. A futex is an ordinary 32-bit word that stays entirely
|
|
// in user memory while uncontended; the kernel is only consulted when a thread
|
|
// actually has to block, at which point the word's address is hashed onto one
|
|
// of FUTEX_BUCKETS wait queues.
|
|
|
|
#define FUTEX_BUCKETS 32
|
|
|
|
typedef enum {
|
|
FUTEX_OP_WAIT = 0,
|
|
FUTEX_OP_WAKE = 1,
|
|
FUTEX_OP_REQUEUE = 2,
|
|
FUTEX_OP_WAKE_ALL = 3
|
|
} futex_op_t;
|
|
|
|
typedef struct {
|
|
uint64_t waits;
|
|
uint64_t wakes;
|
|
uint64_t requeues;
|
|
uint64_t spurious;
|
|
uint64_t timeouts;
|
|
uint32_t active_waiters;
|
|
} futex_stats_t;
|
|
|
|
void futex_init(void);
|
|
|
|
// Sleep on `uaddr` only while *uaddr still equals `expected`. Returns 0 when
|
|
// woken, 1 on timeout, -1 if the value changed before parking (the caller
|
|
// should retry its fast path).
|
|
int futex_wait(volatile uint32_t* uaddr, uint32_t expected, uint64_t timeout_ticks);
|
|
|
|
// Wake up to `count` waiters parked on `uaddr`. Returns how many were woken.
|
|
int futex_wake(volatile uint32_t* uaddr, int count);
|
|
|
|
// Move waiters from `uaddr1` onto `uaddr2` without waking them (used to avoid
|
|
// the thundering herd when a condvar hands off to a mutex).
|
|
int futex_requeue(volatile uint32_t* uaddr1, volatile uint32_t* uaddr2, int count);
|
|
|
|
futex_stats_t futex_get_stats(void);
|
|
void futex_dump(void);
|
|
|
|
// ---------------------------------------------------------------------------
|
|
// A futex-backed mutex, for kernel code that wants sleeping mutual exclusion.
|
|
// ---------------------------------------------------------------------------
|
|
typedef struct {
|
|
volatile uint32_t state; // 0 = unlocked, 1 = locked, 2 = locked + waiters
|
|
char name[24];
|
|
} fmutex_t;
|
|
|
|
void fmutex_init(fmutex_t* m, const char* name);
|
|
void fmutex_lock(fmutex_t* m);
|
|
bool fmutex_trylock(fmutex_t* m);
|
|
void fmutex_unlock(fmutex_t* m);
|
|
|
|
#endif // _KERNEL_FUTEX_H
|