Something more: about general system high-level design

Well, I want to repeat something again, but with more words.

Today I want to introduce intercommunication design within the
whole system.
Firstly, I want to tell - IDL is a good idea in theory and is a bad idea
on practice.
The main reason - it's implementation. IDL usually describe interfaces and,
in addition, creates some code, that packs the request, get it, call it, and, finally,
reply. I.e. receive, call and reply to the message, nothing more.
But, in our system we have something more complex, let's enlist it:

• IPC message forwarding
• Postponed calls (blocking operations)
• IPC message modification operations

Well, on that point you need something more featured than receive - call - reply
cycle, you need to determine when you need to forward a message, on which
point you need to do it, what is immutable message parts and what parts
should be modified and/or cut off.

The other "funny" thing is postponed messages, in this case IDL generated code
must contain many stuff like quick allocation of memory and other stuff.
Finally, generated code is coming to be huge, and in addition you need to modify
it in some different cases.

Another problem is a problem with interfaces, i will try to describe it briefly.
For each instance you have an interface with a predefined set of functions,
many functions are similar, or identical: for example, device has a read() function,
and file has a read() function, but you have a one set of interfaces for file system
and other set of interfaces for devices. That mean that you need to try develop some
generic interface, and extend it every time with your own functions again and again.
On practice you will have a big set of libraries with interfaces and it will be a real headache.

From other point of view, you can resolve the problem with it on the libc client side,
just determine the resource and call specific function i.e. POSIX read() in our case
will call read_file() or read_device() functions depends on the opened resource.
I think - the last idea is very very ugly, I don't think that it's a good idea to change libc
every time when you adding something new to the system, also, we should be modular,
in some cases I can turn off support for pipes of sockets - and I don't want to recompile
libc, all the other system parts for it.

That's why IDL sucks, I spent many time to solve the problems with nontrivial things like
message advanced control and I don't see the sense. But, the old one - uni_rpc_t is sucks too,
on practice uni_rpc_t creates more problems that it's should solve.

And, I faced that pretty solution going from other way to solve this problem.
Each time while you design RPC/IDL/something_else_... you should think more closely
to the system and it's objects, my error was in the way to solve this problem, I think
about RPC/IDL/etc ... only, but you need to think about system also.
What I mean: system might be presented like a set of objects hosted on different servers and
interacting each one with other, and in this case there are no difference between
file and task, i.e. file, task, device, ipc object - it's node, with predefined set of functions.
Well, yes, task and file has a different operations, but all possible operation might
be represented via one set.
Anyway you will have a very similar operations, in example, changing file owner uid and changing
task effective uid is very similar, on RPC level there are no difference between it.
What I decide: I decide to represent all objects (or it's high-level representation) as a node,
each node has a 2 groups of operations, first one for control the node and manage it attributes,
second one for data i/o (yep, task will doesn't have data i/o interface, but we can do it, if needed).
In that case RPC is going to be simple, you have RPC signature in every message,
this signature points to the following things:

• Function group
• Function within group
• IDs to select right node for operation

Other, after RPC signature, is going to the implementation.

How are ipcbox and sbuf abstractions used ?
It's a good question with a brief and simple answer, ipcbox is used by the
rpc library routines to operate with IPC, sbuf is used for data, because implementation
gets the sbuf like a data, rpc code don't allocating anything for implementation,
just sbuf.
Why is it pretty ?
Because it's simple and this solution doesn't require to implement a huge set of
API for each task, i.e. good old getvfspid() getsomeothercrap() bla bla bla.
Each task, has the special system reserved iolink, depends on task role (file system,
regular task, translator, resource carrier, etc ...) its node has a set of operations.
For example, to make a fork() you just need to make a control request via system
iolink to your node with fork() related data, to change your effective uid you just
send a stat request to your node representation, but if you are a regular task (i.e. doesn't have a rights
to link file system onto namespace tree) your node don't have the operation of such kind,
otherwise you will able to make a special call to your system iolink to do it.
Is it simple ? I guess it's very simple solution.

Interest and finance always diverge.

I always tried to combine the work on interesting (and even better on my own) project, and to capitalize on this.
I was never interested in large amounts of money.
I can say that it turned out, several times and with varying degrees of success. And I can do what the findings of these cases, which may be useful in the future.
First, if you managed to establish your own small company for money sponsoring organization, then you should not relax. Financing institution may devour you with your project. In such cases it makes sense to have several organizations concerned with various equity participation.
In general, your own company is a separate conversation.You will not be able to form a small company and develop further in most cases. I'm not a businessman, and therefore can't discuss other ways of creating a company. From the viewpoint of an engineer is better to go a different way. For example, you already have a project that is developed. It's not a secret that the development of the project rather resource-intensive exercise, and intensive development without funding is unlikely. In this case it's necessary to find company, which is interested in such kind of a project. If such company was found, then you hire to work and will assemble a team of specialists. But you shouldn't think then that life was a success, you will have a short time and insatiable wishes of management, and these suggestions will tend to rise.
The deal with the closed project makes no sense in this case - your exciting project will turn into another ugly products, and work on it will be the usual routine. Make your project licensed under free software license (GNU GPL/GNU LGPL), companies offer a product, not a software in most cases. Also, take an existing open and free source code to your project - no one is interested with development all things from scratch.
But don't forget - this symbiosis is not eternal. Ultimately, when your design will come from the door of the research department, the company will not expand the work on your project, instead, your work will be directed to the specific requirements of company management. At this stage it is necessary to separate the project from the company and develop it in an open community of developers. It follows from this - to work on the project is open, and in the broader framework than require your employers.
Well, Jari OS is on this stage now, and I hope that all works on this project will be helpful for community of free software. Also, I will continue works on project with smaller team.
In case of Jari OS, I had a several mistakes: a small open community, not documented internals.

Vnode cache design

I found a development quest in Jari OS: all begins from device drivers services design, some drivers are actually is a library that linking to service that support some hardware part, in this case driver developer folks need to have a dlopen()-family functions to link this libraries at runtime, for example if block service find a specific host it should be linked runtime, not statically. Well, OS hasn't dlopen-family support functions, saying more - dynamically linked ELF support are very early (it works, but it works slowly and takes many service time slice) - the reason is a poor file mapping support, you can map file, but when you will close file descriptor you will got a segfault on page fault in this mapped area. This is a complex problem, to support dlopen() , ELF support should be improved i.e. work with libraries and binaries should be going outside of process manager service and, not be done via read/write calls - one of the benefits will be a dlopen() support.
I know, that one of the weak place of the file subsystem layer is a libv2(it's a VFS-like layer, but implemented as a library that linked to each file system(don't confuse - VFS service is a filesystem manager, resource storage, redirection mechanism and so on)). Libv2 supports many POSIX features already, and operates via abstract vnode_t (in linux it's inode called) and there are too poor vnode cache, so every mapping is connected to vnode and if cache decide to destroy it - mapping can be lost. Like a solution is a map count handling, but it's a very simple - more complex solution is a creating more sophiscated cache.
Assume a file system with a high load, you are always performs lookups, maps, read, write operations - there are possible situation when vnode might not have positive map and open counters for a short amount of time, and there are possible rarely used vnode i.e. some vnode may be mapped sometime, but not accessible for a day - and it will waste you data structure and memory - and you cannot delete it at all. On other side - you cannot use vnode metadata that connected to real file system node, because lookup calls don't modify accessed time of this. Well, what the solution could be - first I determined several vnode stages with it's own features, second - I designed a table for vnodes that mapped, but doesn't accessed - it will not take resources as much as regular vnode takes, but virtually will present.
The next vnode stages might be:

• strong vnode: not a candidate to move to the virtual vnode list, has a positive open and mapped count, and was recently used
• potential oldies vnodes: has only mapped count or opened count positive and wasn't recently used
• oldies vnode: vnodes in the virtual vnodes list
• died vnodes: vnodes that was removed via unlink call

At defined period some thread will lookup the cache and decide what to do with vnode, this rate will be calculated by the file system activity (calls per last period). But what about died vnodes? Assume that you mapped file, somebody remove it, vnode id was taken by root only file ... well, died vnodes list as a low cost list that storage vnode of this types and when you will try to read or write to it, or you will unmap it, or got a page fault - information will be updated - you will got an error (or seg fault), file system will decrement the counters, and when this counters will zeroed - died vnode will go to heaven, and free it's id ;)
I'm not sure that I will implement all features at near time, but anyway this functionality will be added to libv2 - and I will continue my quest - I will improve page cache, improve memory events protocol, design and implement linker with dlopen ;)

SDK tools for OS development

New ideas came to my head, all about operating system features and development.

On last friday I decide to make some modifications on autotools stuff in GNU sed and try to compile it with Jari OS libc headers and functions. Yep - it's works! This means that our libc is ready for most of cases, many of them working now. This event gave me some new ideas about development tools for Jari OS: firstly I will port GNU gcc to Jari OS (I mean, that gcc will handle our ld scripts and libraries right, without many keys and other things), secondly I will construct SDK template (already done, but not publicied yet).
Also, to have a better support and big community additional feature needed - IDL integrated to SDK. Well, it's mean - that you have set of the templates for each type of service i.e. block device driver library, char device driver, file system and so on ...
In most cases you shouldn't known about specific internal things of system libraries, also you shouldn't care about interface changes (headers renaming, new functions, new order of calls and so on). This feature will generate libraries specific code in compile time and link your specific implementation. I.e. what will be written one time - will live all time ;)
For this feature it's better to use scheme (for templates, configs and other stuff) and some core of this will be written traditionally on C.

Jari OS going to be a completely OS

My last task in Jari OS project was symlinks supports, now I'm working on postponed logic in libv2 (general library for file system services).
I cannot be on track in changes ;) Now project has a POSIX, fork(), execve(), file systems, initial networking support.
On background I'm porting GNU coreutils to Jari OS, progress going fast, I think that alpha release will has many interesting stuff.
To be a fully featured OS not so many features need, our ext2fs support and IDE drivers are 80% completed.
I think that year of active development that will finished on 1-sep-2009 will made a first beta version with few drivers and networking support.
Now prject has one network device support (e1000) and Jari OS host (network service) replies on ICMP requests.
What about ELF support, now we're working on dynamic libraries support - it coming soon, currently only static ones supported.
Files i/o is ready, but maybe some functions (not often used ones) doesn't works properly. To make a fully featured shell pipes requered, and I'm working on it now.
I'm planning to implement shared memory fs and POSIX functions for it, in addition I will add Jari OS specific API for this, - for some internal purposes, for GIX(GUI service of Jari) like example.
After alpha release (1-jun-2009) I will take time for GIX implementation. Also - there are many porting tasks.
I hope community of open-source developers will be interested in new microkernel OS - it's a good field for research, development and it's good to take skills up-to-date.
So,

Jari OS: fork() in microkernel based OS

Well, this day makes huge parts of my brains works.
Designing microkernel systems you have a good skills base, designing microkernel and multiservice system you have an excellent skills base.
Today was a day of fork() call - it has many things to discuss, think, imaginate and so on.
At the end of a day, after all problems was detected - I found a solution to solve fork() call.
Let's begin and I will explain fork() nature as is...
Fork is a POSIX call that creates a clone of a calling process - with one thread, but the clone should have the same resources - i.e. memory (not at all), opened file descriptors, IPC stuff.
In Jari OS resources are isolated - VFS know about files, kernel knowns about IPC and so on - you will have a headache about syncronization, performance - always while architecture design - welcome to microkernel-based OS.
In this case you need to develop non-trivial trick with things that monolithic kernels made easly, but ... microkernel-based OSes is clever and better at all.
Well, you have a task, you have a resources and you need to fork() POSIX call - the first solution is simple - just delegate this job to process server and deal is made, within server timeslice - and this is bad (but QNX does it in this way). Other solution is more sophiscated - and you need to make a stages for fork():

• Request to delegate a fork() for myself
• Make a fork() skel within my timeslice
  
• Send a request about fork() call made by me

In this big deal you will affect microkernel, process service, virtual file system service and your task.
Going deeper I will explain each stage of fork() and after those I will explain how it works on different sides.
Your first request is a request to the process service where you tell that you wants to make a fork(). Process service will create a mould on VFS of your resources, toggle bit in kernel that allow you to make a sys_fork() syscall, and if all is ok it will reply with ok message :)
After this you are going to make a syscall to fork - be warn! kernel toggle off bit that allows you to make this call, and you cannot do it yourself - only trusted process service does.
Call is done - you have a skel - you are making a second call to process service - i.e. - "fork is done - please make my child runnable" - process service tells VFS to make mould active and working - and changes status of the child - and replies you with "OK all is done".
This scheme allows task to make a one fork() call at a time (i.e. you are able to make other child after old child is created) - I don't think that this is a bad, other architecture going to make other applications design.
On this I want to explain some details.
"Forkable bit" can be toggled on only by trusted process, and it's switched off while fork called.
Task has a timestamp - and both kernel and process service known it at the start of all.
VFS's mould has a parent and while parent is exist - mould will not be deleted, orphaned mould will be deleted with timeout.
Checking for a valid child pid makes not only on parent pid - also on timestamp.

Uff, I can explain other details in comments.

File systems on Jari OS

There was a great job on last two weeks. File subsystem are designed in Jari OS - since we have a system with separated services - libraries is a good approach to avoid a huge amount of code and errors with changes it.
Actually file subsystem is divided by several general parts:

• VFSv2 service
• set of libraries for each filesystem

I don't want to include all stuff for filesystem in one library, because it's a bad idea, for example tmpfs doesn't has backend to block device, pagecache, postponed calls and so on. But anyway this set of libraries can be completed by one, generic library that should be included to each file system - libv2.
In this case we're have the following list:

• libv2 (general library)
• libv2backend (backend to the block device layer)
  
• libv2pgcache (page cache library)
  
• libv2ppcall (library serves postponed calls)

Each file system architecture should determine what will be used, generally , regular file system will always use all set of libraries - i.e. it works with block device and use page cache in this case, and it will not replies immediately on all cases - it will have postponed calls list to reply.
For libv2 - there are nothing difference - it will always support everything on logic layer.
I can't see other solutions - our VFS service should be overloaded - and many calls going directly to file system service.
So, while implementation tmpfs and initfs - implementation hasn't any complexities.

Jari OS: device drivers development wellness

I have a lot of time spent with drivers development in different OSes/kernels. Generally it was microkernel or hybrid kernels and I cannot told that this process takes me into pleasure.
Jari OS on other side is a new microkernel OS that can takes in advance all my skills with system design.
Actually every Jari driver is a microkernel service working in userspace like a trusted task. All IO mechanics has a protocol and every time you need to support it with all changes. It's a bad, but for this case I've designed a generic device server layer that will hide all semantics within several library functions.
All of this located in system libraries - in LibOS part.
Include and you will have server implemented. Really is a generic layer - on top of this I will design and implement other layers - for console drivers, input drivers, block drivers and so on.
Like example of this I will show a code snippet of the generic VGA console driver uses this generic layer:

#include <sys/types.h>
#include <sys/mman.h>
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <string.h>
#include <wchar.h>
#include <errno.h>
#include <time.h>
#include <datalib/usrtc.h>
#include <ns/ns.h>
#include <scheduler.h>
#include <proto/rpc.h>
#include <devio/devio.h>
#include <devio/server.h>
#include <termio/termio.h>

#include <termio/term.h>

#include "vga.h"
#include "hwops.h"

#define DRVNAME  "vgacons.d"
#define DEVNAME  "/console"

static size_t __vga_write(void *buf,uni_rpc_t rpc,size_t size,size_t offset);
static size_t __vga_read(void *buf,uni_rpc_t rpc,size_t size,size_t offset);
static int __vga_ioctl(void *buf,uni_rpc_t *rpc,size_t size);

struct device_ops dev_op = {
  __vga_write,
  __vga_read,
  NULL,
  __vga_ioctl,
  __vga_write,
  __vga_read,
  NULL,
  NULL,
};

int main(int argc,char **argv)
{
  device_server_t *sys;
  int r=0;
  void *iobuf=mmap(NULL,4096,MMAP_RW|MMAP_PHYS,NOFD,(void*)VGA_TM_BASE);
  char buff[256];

  task_scheduler_control(getpid(),SYS_SCHED_CTL_SET_PRIORITY,30);

  vga_init(iobuf);

  vga_print("[vgacons] i've started\n");

  sys=malloc(sizeof(*sys));
  if(!sys)
    abort();

  r=init_device_server(sys,DIRECTIO_READ | DIRECTIO_WRITE | HW_READ | HW_WRITE,
                       2048,4096,512,1,DRVNAME,DEVNAME,&dev_op,4);

  sprintf(buff,"sys->allowed = %p\n",sys->allowed);
  vga_print(buff);

  if(r!=0) {
    sprintf(buff,"r=%d\n",r);
    vga_print(buff);
    abort();
  }

  vga_print("[vgacons] device server run\n");

  device_server_start(sys);

  vga_print("[vgacons] :((\n");

  return 0;
}

static size_t __vga_write(void *buf,uni_rpc_t rpc,size_t size,size_t offset)
{
  char *msg=buf;
  size_t rsize=size;

  if(size<=sizeof(rpc)) {
    return -EINVAL;
  }
  msg+=sizeof(rpc);
  size-=sizeof(rpc);

  switch(rpc.arg3) {
  case PHYT_WRITE:
    uni_print((cschar_t*)msg,size);
    break;
  case PHYT_WRITEPOS:
    uni_printxy((cschar_t*)msg,size,rpc.arg4,rpc.arg5);
    break;
  case PHYT_SCROLL:
    if(rpc.arg4==SCROLL_UP) {
      uni_scrollup(rpc.arg5);
      uni_printxy((cschar_t*)msg,size,0,0);
    } else if(rpc.arg3==SCROLL_DOWN) {
      uni_scrolldown(rpc.arg5);
      uni_printxy((cschar_t*)msg,size,0,uni_height()-rpc.arg5);
    } else
      return -EINVAL;
    break;
  default:
    return -EINVAL;
    break;
  }

  return rsize;
}

void ascii_puts(const char *msg)
{
  return;
}

static size_t __vga_read(void *buf,uni_rpc_t rpc,size_t size,size_t offset)
{

  vga_print("ridden\n");

  return 0;
}

static int __vga_ioctl(void *buf,uni_rpc_t *rpc,size_t size)
{
  uni_rpc_t rrpc;

  if(size<sizeof(rrpc))
    return EINVAL;

  memcpy(&rrpc,buf,sizeof(rrpc));
  switch(rrpc.arg3) {
  case PHYT_DISABLEAUTOSCROLL:
    uni_scrolldisable();
    rpc->rpc_call=0;
    break;
  case PHYT_ENABLESCROLL:
    uni_scrollenable();
    rpc->rpc_call=0;
    break;
  case PHYT_GETSIZE:
    rpc->rpc_call=0;
    rpc->arg0=uni_width();
    rpc->arg1=uni_height();
    break;
  case PHYT_CLEAR:
    uni_clear();
    break;
  default:
    return EINVAL;
    break;
  }

  return 0;
}

Jari Operating System: reburned

I don't have a time to write more.
This is just a copy-paste from news feed:
After Jari was frozen for a many years, now Jari is wake up and preparing to work, for a hard work.
Jari Operating System will be a not microkernel/hybrid based system, otherwise it will use an exokernel, that developing separately. It's mean that Jari Operating System is a set of user-space drivers, network libs, libOS, libc and so on. It's a top level of a exokernel.
While exokernel under extreme development stage and not all syscalls are well defined, this project will wait for this and will temproary suspended (for several weeks or one month, it cannot be determined now). After those userspace wrappers will be implemented and user-space development begins.
After core libs are well tested and exokernel will be done this all will be ported to it.
In case of exokernel Jari changing default architecture to amd64 (not x86_64, just amd64 in case of its specific hardware features), but Jari portable, and all depends on exokernel ports.
So, I will present an exokernel -> http://mstring.jarios.org , it's called MuiString (greek mui at the begging) that shows it's small size, and string just a mode for kernel flexibility and atomicity (you know about string theory).
Generally it mean that Jari found a kernel to base on, ... it was a
long search ...

Also I want to introduce a new Jari OS homesite - http://jarios.org, you can find a lot of
information there.

Thanks.

ReadLeaf: updates

I want to make announcment.
ReadLeaf 0.2alpha is out with many new features.
You can look out for more info here - http://www.readleaf.org

ReadLeaf: research pane

Today, how I've wrote later, readleaf 0.1 was released and finished lazy stage - now it's a platform for research and implementation.
Both, MuiString and ReadLeaf has a one general idea, but MuiString is more deeper in implementation and some decisions need to be tested on other layer - quick and fast before this innovation will be implemented within MuiString and Jari overally.
ReadLeaf is a good start point for this type of research, I will use new way in development primary here - in area of the project.
I'm too lazy for repeations - you can see the general overview here - http://readleaf.berlios.de/concept.html
Currently already implemented:

• redleafd
• internal mm
• basic research

Version 0.2 will be already with new features, now it's on the testing and development stage, but not so long from finish.

MuiString: Introduction to the architecture #1

Today we're have a many implementations of the microkernel architectures, but there are too similar and have many problems.
The first problem is a speed, the second one is a security.
Generally microkernel more secure than monolithic-based operating system, but with some restrictions, if you grow up speed, you are loosing in security.
But it's a general problems - more complicated thing - we're using C/C++/ObjC to implement architecture, and there are language takes a many time and limits in the implementing.
My general idea is to use a functional programming language - and I've choose scheme - it's better, simply.
Look for the block diagram:
MuiString separated to the three logical parts, the first low two layers implemented on C (or on Cext in future), the third layer implemented on C/Cext and on scheme itself.
All hardware specific things are hidden in the MuiString.
All services should be implemented on scheme, yes, we're can use C-written servers and libs (it should be done for liblinux/libposix), but in general case all other will be implemented on scheme and ran on scheme VM.
All IPC will be operate via scheme forms - in this case all security models will be implemented without IPC calls restrictions, and it can be made on the VM (or language) level.
There are several security models and several objects on the higher level:

• Trusted servers
• Key signed
• Group politics

Trusted servers can allow secure transmit via determined servers, for example - you trust to the TCP/IP server, LAN server also trust it, but there are no directions from you to the LAN server, but LAN server and you can get access to execute scheme forms from/on LAN server, because there are trusted via TCP/IP server.

I will write more researching results in the next post.

Tips'n'Tricks: GCC useful macros for debugging

Continuing my series for newbies/beginners I want to told about gcc macros useful for debugging.
Everytime on C you have deal with memory, and very big part of bugs are memory managing related.
You must know differents ways to decide question with it, wrappers to general mmap/malloc/munmap/free functions, implement your own allocator (if you really know what you're doing).
Anyway, it's better to know without debugger (just use stdout to make this deal) when you are allocate and freed memory. GCC has a several really useful macros for this.
For example let's write a simple example with free() function:

void *__my_free(char *file,int line,char *function,void *p)
{
 if(p)    free(p);
 else     {
   fprintf(stderr,"Trying to free nil pointer.\n");
   fprintf(stderr,"At `%s:%d' via '%s'\n",file,line,function);
 }

 return NULL;
}

It's really a big shit deal to point everywhere info about function, line and file ;)
Just use this macro:

#define my_free(p)  __my_free(__FILE__,__LINE__,(char *)__FUNCTION__,p)

This is all, for more detailed documentation see gcc manual.

Memory management - buddy system trick.

How I wrote before, on low level we're need a simple and fast allocator with minimal external fragmentation. It was buddy system. I've used a binary buddy in case of simple and clean code and perfomance.
But we're need to store a free buddies list, but we haven't any allocators lower and we're cannot allocate something for it, and we're cannot create linked list of pointers to the blocks and chunks - and it's not so clever - the really big overdraft on it.
Theory:
I've decide that I can use a bitmap in this case, for grow up speed I will use a bitmap for each buddy list level in this case for first level we're need just 1 bit per attribute, for second 2 bits per attribute ... and so on. Also we're need to make a simple initialization and keep information about separating. In this case we're using 2 bits per buddy block, I've called them - the first one is negative bitmap, the second one is positive bitmap.
What are they means? The first bit attribute (negative) points that if the bit is set it's a free block, if not it's used (or unmapped) block. Second bit attribute (positive) points that if the bit set it's not separated block, otherwise is. In this model we're simply full negative bitmap with 0x0and positive bitmap with 0xffffffff, and how you can understand we will use unsigned integer 32bit sized ones for bitmap.
Make a simple calculations and you will get a good news - for map buddy with 16-parts you need 64bits or 8 bytes, isn't pretty?
Implementation:
So, the first I will declare the general structure that will describe buddy system:

typedef struct __bbuddy_type {
  uint32_t *pbmp;
  uint32_t *nbmp;
  uint32_t pn;
} bbuddy_t;

How you can see there are two pointers and what the neck ?
So, I'll explain it - on low level you need to take a pointer (determining the size you need) and use it for your first buddy - it's simply than something else. Also, I store buddy_t first and after it I'm storing uint32_t data.
Also we're need an macro that will calculate the overall size to store the buddy system, let's take it:

#define bbuddy_size(n)  (((((n/32)==0) ? 1 : ((n/32>1) ? (n/32)+2 : n/32+1))*(2*sizeof(uint32_t)))+\
                         sizeof(bbuddy_t))

Explaining it, for parts that bigger than 1/32 of buddy mapped area we're need just one uint32_t , for 1/32 yet another one, and for smaller parts working a general rule to calculate size. Like in squares roots calculation ;)
Also you will need for several useful macros that will calculates index of pointer and bit position within bitmap area:

#define bbuddy_indexp(p,n)  ((p/32 > 1) ? ((p/32)+(n/32)) : p/32)
#define bbuddy_indexbn(n)   ((n/32>0) ? n%32 : n)

The first macro will calculate index to choose correct uint32_t data, and second one to choose a bit position, be careful using this macros as is not a good practice, I will show examples of using its.
In the implementation explanation I don't want to show you all the source code, it's a simple - you can implement it yourself without any kind of problems.
But there are some useful code snippets I'll show. 
The first point on implementation is initialization of buddy system, assign a correct pointers for bitmaps, init first block free. Here be careful with pointers shifting deals, I will show you the simple one, that works correctly, but don't forgot that C operator '+' on pointers shifts pointers with the size of  pointer type.
I've used char* - it's a clean and transparent to understand:

uint8_t bbuddy_init(bbuddy_t *b,uint32_t max_part)
{
  int yy=(max_part/32)*2,i;
  char *ptr=(char*)b;

  if(b && max_part) {
    ptr+=sizeof(bbuddy_t);
    b->pbmp=(uint32_t*)ptr;
    ptr+=(sizeof(uint32_t)*((max_part/32 > 1) ? (max_part/32)+2 : (max_part/32)+1));
    b->nbmp=(uint32_t*)ptr;
  } else
    return 1;

  b->pn=max_part;

  max_part/=32;

  for(i=0;i<yy;i++) {
    b->nbmp[i]=nil;
    b->pbmp[i]=fil;
  }

  /* init first */
  b->nbmp[0] |= (1 << 0);
  b->nbmp[0] |= (1 << 1);

  return 0;
}

NOTE: nil it's a macro defined to 0x0 and fil is a macro defined to 0xffffffff.
Here we go ... we're a correctly init buddy system structure.
Now, I want to wrote about allocations/splitting/freeing specifics of this implementation.
I've implement an allocation function with mind that I've giving a part number of buddy system and it's trying to return me a number of avialable and allocated part. Look below:

static uint32_t __bbuddy_block_alloc(bbuddy_t *b,uint32_t align,uint8_t m_flag)
{
  uint32_t p_indx=align/32;
  uint32_t n_indx=0,i=0,o=0;

  if(p_indx) {
    for(i=0;i<p_indx;i++) {
      if(b->nbmp[p_indx+i]!=0x0)
        goto __is_free_long;
    }
    m_flag++;
    return __bbuddy_block_alloc(b,align/2,m_flag);
  }

  if(!p_indx) { /* checking small layers, big blocks */
    o=align*2;
    for(i=align;i<o;i++) 
      if((b->nbmp[p_indx] & (1 << i)) && !m_flag) {
        b->nbmp[p_indx] &= ~(1 << i); /* used */
        b->pbmp[p_indx] |= (1 << i); /* not separated */
        return i-align;
      } else if((b->nbmp[p_indx] & (1 << i)) && m_flag) {
        b->nbmp[p_indx] &= ~(1 << i); /* used */
        b->pbmp[p_indx] &= ~(1 << i); /* separated */
        /* mark childs free */
        align*=2;         i*=2;
        p_indx=align/32;
        n_indx=bbuddy_indexbn(i);
        b->nbmp[p_indx] |= (1 << n_indx);
        b->nbmp[p_indx] |= (1 << (n_indx+1));
        b->pbmp[p_indx] |= (1 << n_indx);
        b->pbmp[p_indx] |= (1 << (n_indx+1));

        m_flag--;
        return __bbuddy_block_alloc(b,align,m_flag);
      }
    if(i<2)
      return ENOBLOCK;
    else {
      m_flag++;
      return __bbuddy_block_alloc(b,align/2,m_flag);
    }
  }

 __is_free_long: 
  while(o<32) {
    if((b->nbmp[p_indx+i] & (1 << o)) && !m_flag) { /* yep, found */
      b->nbmp[p_indx+i] &= ~(1 << o); /* used */
      b->pbmp[p_indx+i] |= (1 << o); /* not separated */
      return (p_indx > 1) ? (((p_indx+i)-2)*32)+o : o;
    }
    else if((b->nbmp[p_indx+i] & (1 << o)) && m_flag) { /* make sep */
      b->nbmp[p_indx+i] &= ~(1 << o); /* used */
      b->pbmp[p_indx+i] &= ~(1 << o); /* separated */
      /* mark childs free */
      align*=2;        p_indx=align/32; o*=2;
      p_indx=bbuddy_indexp(align,o);
      n_indx=bbuddy_indexbn(o);
      b->nbmp[p_indx] |= (1 << n_indx);
      b->nbmp[p_indx] |= (1 << (n_indx+1));
      b->pbmp[p_indx] |= (1 << n_indx);
      b->pbmp[p_indx] |= (1 << (n_indx+1));

      m_flag--;
      return __bbuddy_block_alloc(b,align,m_flag);
    }
    o++;
  }


  return 0;
}

How you can see there are difference between 1/16 and bigger parts - I've showed it, it's separated via source code implementation in case of making additional checking and different calculation in both situations, you can split there parts into one to make code lines counter smaller , but it doesn't give any perfomance effect (tested).
Freeing buddy block must be assigned with splitting buddy into bigger block if possible, I've implement this via recursive separate function to make a lightweight to read release function, also I will point to indexes calculations here. 
And I want you to understand, I'm giving to release function number of smaller blocks like offset to release, after those I'm calculating possible variants of blocks can be and if found I'm releasing it, and only after it I'm calls my splitter function. Also, I don't include additonal checking code, make it yourself ;), look below:

static uint32_t __bbuddy_block_release(bbuddy_t *b,uint32_t num,uint32_t i)
{
  uint32_t p_indx,n_indx;
  uint32_t layer=b->pn,ls=layer,a=0;

  /* first look up on higher possible layer
   * if there are now, look deeper
   */
  if(num>b->pn)
    return EINVALIDINDX; /* error encount */

  while(ls) {    ls/=2; a++;  } 
  if(i==0) {
    for(i=(a-1);i>0;i--) {
      if(num%2) break;
      else num/=2;
    }
  } 

  layer=(1 << i);

  n_indx=(layer<32) ? (num+layer) : bbuddy_indexbn(num);
  p_indx=bbuddy_indexp(layer,num);
  if(!(b->nbmp[p_indx] & (1 << n_indx)) && (b->pbmp[p_indx] & (1 << n_indx))) { 
    b->nbmp[p_indx] |= (1 << n_indx); /* mark free */
    return __bbuddy_split_up(b,layer,num);
  } else if(!(b->nbmp[p_indx] & (1 << n_indx)) && !(b->pbmp[p_indx] & (1 << n_indx))) { /* going deep */
    i++;
    if(i>=a)
      return EBUDDYCORRUPED;
    else
      return __bbuddy_block_release(b,num*2,i);

  }

  return 0;
}

In case of my initialization and implementation of bitmap, I'm starting to look up for the block from the biggest blocks, because in othercase there are will be errors on cleanly initied bitmap and buddy will corruped.
Also, I don't want to describe my splitter function and I will not show it's source code - it's a trivial too like others.
Be patient, on my code (I wrote it and tested within 1-2 hours) some checks is absent, and some code I've specially removed - take your brains on working way ;)
Like API functions I've made a wrapper to hide all recursion in static functions, and with assign of initial counters values.
On next post I will try to explain how we're can use this abstraction to allocate real pointers, or you can think yourself and assume this method - it's a too trivial ;)

Memory management - low allocator base - binary buddy.

As I intended to memory managers implementing, I decide to write here about several techniques about this.
I don't interested on allocators in uspace now. I want to describe some tips and tricks on memory management while you haven't anything - just raw gdt/tss/ so on and raw addresses.
On low level of memory management and allocation system we're need to have a simple and fast memory allocator, it must avoid external fragmentation as strong as it possible.
There are one good allocator that doesn't sick with big external fragmentation - buddy system. You can find many it's types, but I'd like binary type - it's a very simple in calculation (that really needs).
Some words about buddy system... Buddy system is a such system that based on buddy relations for splitting memory areas. This system has several limitation - you must know deep of separation, I mean how much blocks maximally can contents buddy itself, and overally it can maps fixed memory area size (but it can be depends on implementation). The goal of this technique is to find free block aligned to requested size, when you are looking for some block size - you will separate block with bigger size and so on, while you didn't finf more situable block size. Look for illustrations: 

Fig. 1
The first bar shows clean buddy system without any allocated block (4096 bytes). When we're requesting to allocate block with size 512 byte we're separate zone to two blocks, and one of this zone separate we're separate too and use one of them - like it shown on the second bar. If we're request to allocate three more 512-sized block we will got the picture displayed on third bar.
It's a good and relativetly fast methodics, but has many restrictions - for example assume that your buddy system has 16byte-sized minimal blocks - and you request 10 bytes - so, you will get a wasted space - and so on - it's an inernal fragmentation. Be sure - you can align block sizes to other numbers , like you want and depend on your target, but anyway it will not safe to use buddy for all allocations.
Another point is a free/busy/separated blocks list storing - on low level you cannot use binary trees in case that they need to have some memory allocation technique already, usually for this used simple pointers lists, but it's a worse practice.
On the next post about memory management I will describe my solution of this problem with some useful code snippets.

MuiString higher memory management

I've made some researching and emulation (not so serios, but representative) about memory management in microkernel OS.
Many kernels does memory management fully in kernel space, others separate it and offer non-trivial API for doing this in userspace.
We're have many restrictions - security and performance. If you will targeting to one of this properties you will loose on other. If you want to have a very strong and secure mechanism you will make a many context switching within kernel and user spaces - it will slow down your system perfomance, if you will don't care about security you will make it faster ...
I decide to make a basics virtual memory manager operations within kernel space, and offer simple API (just 4 calls) - address_space_get(), address_space_set(), address_space_alloc(), address_space_release(). And ... bind page fault exception to userspace area virtual mm server.
In this scheme microkernel just mark/unmark address space, it doesn't makes a check (and it will works fast) , and microkernel doesn't care about page fault exception - it's a server headache.
The security implemented on userspace - with ACL server that cannot be exchanged - like other varios servers (you must load its via multiboot modules way), all requests to ACL cached to the IPC cache server (it cannot be exchanged too) to avoid premiary access violation checks and grow up speed of requests. On the figure below I've tried to show it graphically (I like this, but I don't like to make a graphics ...):

User task just trying to take some virtual memory and extend it's address space - it's a deal of libs to make all job with calling of vmm server. Vmm server asks about access rights/limits/etc ... on ACL server, if all granted - vmm will allocate space for user task, if will be need - it will calls MuiString microkernel via simple API.

This structure allows to make secure and fast (compairing with some highly secured or highly fast microkernel systems) - it's a good design for implementing different models of memory allocations (real-time, preemption, so on ...)

AMD64 #1 - Long Mode

Backing to old days the first tree of microkernel was targeted to the x86 (32bit), going deeper the parent of all post projects (ilix) was targeted to embedded hardware i.e. arm and one internal architecture that was 24 bit.
Nowadays we're have a public accessible and cheep 64bit long architecture, x86 continuing but with 64bit long extension, but on real - it's looks different.
AMD64 allows many good extended features compairing with basic x86 32bit long structure. To use AMD64 features on full filled hand we're must operate in long mode (amd64 specific mode).
On truth, long mode is a mixed mode i.e. it operates on 64-bit mode and compatibility mode at one time. It has self minuses - it's a flat memory model. But it has 64-bit addressing and we're don't need for tricks with extension from intel to use more than 4Gb address space addressing, that relatively ugly and looks like an ugly hack.
Like a microkernel developer and low developer at one time - the first problem is initialization.
I've read AMD64 documentation directly from AMD, but there are no anything to really help with it, not at all, but if you want to make a sense quickly it's not usable.
I've designed a trick with it, saying simply it consist from following steps :
32bit code:

• - initialize stack pointer (regarding your boot method and loader, I'm using grub and multiboot)

• - init bootstrap GDT

• - jump to 'meet point' within existing GDT

• - save parameters from grub (will be need on if you using grub)

• - we're falled on 32bit protected mode (legacy mode on AMD64)

• - check for varios CPU features (it must be made if you want to made all like it must be in good kernels)

• - check for AMD64 long mode support is a really needed (you should do it, otherwise you can except some bug - I don't know why - check it if I correct)

• - all is ok, - enabling 64bit page translations (regarding to documentation set - cr4.pae=1)

• - setup pages tables

• - enable long mode (via EFER reg - setting LME to 1)

• - enable paging in long mode (it will activate long mode and we're falling to compatibility mode)

• - just jump to your 64bit code
  

64bit code:

• - do your stuff, have a lot of fun ... ;)

I'm sure that there are direct long mode switching, but for me it was more quickly to make it like I've describe.

MuiString introduction

Ok, I've told many information about Jari and so on ... But it was just a buzz words.
Now I want to present MuiString (mstring) microkernel project.
What is done?
- base structure
- low level stuff
How much time it will takes ? How long will I told about it without microkernel on legs ? Hm, so I think that this times ends in case of microkernel progress.

I promise to write more technical things here and ... look for links below -
MuiString homepage - http://mstring.berlios.de
MuiString wiki - http://mstring.berlios.de/wiki
I have a memory manager and core of scheduler in my sandbox, it's under testing and preparing to be committed to the general CVS repository.
Look for my messages here soon.

Thanks.

Web fun - redleaf

How I wrote before - I opened a new project just for fun - and now it has releases and it's working - http://redleaf.berlios.de
But there are no time for prolongate any active development - I've spent less than 10 hours for this, and in future this will so.
If you want to take my flash point on this project - contact me, I'll be glad for it.
Anyway, this project will be like my testing platform - and some kinds of tasks will be implemented within this and tested.

Decomposing big project, separating is better

You can find more information on the link in the post title.
Overally, following to the general idea - "separate all works and job to smaller ones" I decide to run microkernel separatly - like independed project.
This intended to be more effective, for example - currently I have EZA layer working for 60% (not so stable) and this was made after reorganization of the microkernel structure - and this just for less then 10 hours of normal works on the problem.
MString (MuiString) - is a name for Jari microkernel - and it's a new tag on this blog ;)
Now I'm thinking on diferent than C/Cext language for server space - it's a big flame, but I'm thinking that fully functional languages or partly functional is better than typical imperativies ones. Anyway, microkernel must be implemented on plain C - it's more comfortable language.