Kernel utilities

Kernel Utilities

The kernel is not an ordinary application. You don't have any runtime or standard library to guide you in and no debugging utilities. The lack of underlying system make things more complicated. However a clean design, good testing and sufficient discipline will make those easier to handle.

For this reason, part of the kernel is dedicated to utilities routines. In order to build reusable and testable components, several features have been implemented as the standard library.

String manipulation

The kernel embeds it's own copy of string.h and implementation. This part of the standard is almost standalone. As such every symbols defined on string.h can be considered as available for kernel code.

The kernel should be able to handle unicode characters. The default encoding should be UTF-8 but it might be nice to have its configurable at compile time.

Unicode support is not provided yet but I planned to use the same layer as Microsoft tchar.h. The current header for strings is made to be easily declined into wchar.h or mbstring.h.

We shall always use str*() method right now, and once unicode support will be provided, we'll replace them with _tcs*().

• _tcs---() => { str---(), wsc---(), mbs---() }
• _istc---() => { is---(), isw---(), ismbc---() }

Memory allocation

Memory allocation on kernel is a bit tricky. As the system will create tons of structure and release them and need to be stable over a long period of time, heap fragmentation is the one thing to avoid.

Memory mapping

The basic feature for memory allocation is pages mapping. On a user space program this is offer using mmap() and munmap() routines. This allows to create some areas into the virtual address space.

The kernel has some similar feature for it's own address space. Those are named kmap() and kunmap(). Both rely on the same implementation where options differs a bit.

kmap() doesn't take hint address. On Kora, fixed address mapping isn't recommended. It doesn't solve any issues but breaks portability. It mmap() keep the feature for compatibility, his usage is prohibited.

Memory mapping must be the default allocation method on the kernel as soon as requested size pass the K-byte.

Heap

For smaller allocation, we use a regular heap implementation.

I use the exact same algorithm for my kernel and libc, relying on a map/unmap pair (not sbrk()) which differs on both environments. The kernel code redirect to kmap() where the libc use syscalls. The implementation is a multi-arena heap where each arena is a fixed size anonymous memory mapping.

A fixed size arena is easier to handle the free blocks are linked to each other in order of sizes for fast allocation and adjacent blocks are merged to each others. The free list is one solution, but I preferred it over binary tree, even if the complexity disagree. The tree might grow much in size and become costly to rebalance while the list can easily be optimized using anchors to key sizes. In both cases, heap algorithm are terrible in terms of CPU cache.

The heap features will probably stay on the kernel at least for string allocation. Those can be allocated by malloc()/free() routines.

For kernel structure, we should use kalloc()/kfree()routines. At this moment it use malloc() and reset clear to zero. However this routines might be migrated to a slab allocator.

Formatting and Conversion

Numeric Conversion

Time

Format

Synchronization

Spinlock

Read-write lock

Futex

Mutex

Condition

Data containers

Doubly linked list

Balanced binary tree

Hash map

Lock free priority queue

Atomic operations

Data size

Note : time_t, size_t, off_t, CSTR

Syslogs