SQLite tree structures and queries to get sub-trees

SQLite is wonderful!

Just today I found that SQLite support queries with a recurse to get the inner sub-trees:

CREATE TABLE els (
  id INTEGER PRIMARY KEY AUTOINCREMENT NOT NULL UNIQUE
  ,pid INTEGER DEFAULT NULL REFERENCES els
  ,name TEXT
);
INSERT INTO els (id, pid, name) VALUES (1, NULL, 'top');
INSERT INTO els (id, pid, name) VALUES (2, 1, 'x2');
INSERT INTO els (id, pid, name) VALUES (3, 1, 'x1');
INSERT INTO els (id, pid, name) VALUES (4, 3, 'y2');
INSERT INTO els (id, pid, name) VALUES (5, 3, 'y1');
INSERT INTO els (id, pid, name) VALUES (6, 1, 'x3');
INSERT INTO els (id, pid, name) VALUES (7, 6, 'w2');
INSERT INTO els (id, pid, name) VALUES (8, 6, 'w1');
INSERT INTO els (id, pid, name) VALUES (9, 7, 'z1');
INSERT INTO els (id, pid, name) VALUES (10, 7, 'z2');

top
|-x1
| |-y1
| |-y2
|-x2
|-x3
  |-w1
  |-w2
    |-z1
    |-z2

We can write SQL query to get all children of element x3 (id=6):

WITH RECURSIVE
  els_cte(id,pid,name) AS (
    SELECT id,pid,name
        FROM els
        WHERE pid=6
    UNION ALL
        SELECT x.id,x.pid,x.name
            FROM els AS x
            INNER JOIN els_cte AS y ON (x.pid=y.id)
  )
SELECT id,pid,name
    FROM els_cte;

Results are:

7	6	w2
8	6	w1
9	7	z1
10	7	z2
Posted in Blog, Ideas, Misc, Research, SQLite | Leave a comment

Ru: Archive: Делаем свою Time Machine для Линукса (2012)

После интенсивного пользования time machine на маках и пару ситуаций когда она реально пригодилась (были варианты когда пришлось поставить систему из бэкапов и варант когда пришлось откатывать назад после проблем), возникла мысль а собственно почему такой удобной системы нет на линуксе. После исследования вопроса и опроса знакомых линуксоидов оказалось что:
1. сделать такую систему можно Read More »

Posted in Blog, Gentoo, Ideas, Misc, Research, Ru, Tutorial | Leave a comment

Ru: Archive: Небольшой эксперимент сетевой независимости (2013)

Где-то год назад я решил для себя провести небольшой эксперимент. Я заметил что привязка к облачным сервисам становится всё более проникающей, и подумал проверить — что собственно нужно для того, чтобы немного отвязаться от серверов разных корпораций бобра.

Задача была в том чтобы попробовать насколько мощное или простое железо нужно для небольшего домашнего сервера Read More »

Posted in Blog, Gentoo, Ideas, Misc, Research, Ru, Web | Leave a comment

Ru: Archive: Шифруемся в Qt (2013)

Так как оказалось, что наши коммуникации довольно легко просматриваются товарищами из АНБ то похоже что нужно шифровать все коммуникации. Я решил проверить насколько сложно подключить шифрование в разработке Qt приложений. Как оказалось что все совсем несложно даже в случае использовании PGP.

Так что тут больше дело привычки разработчика чтобы шифровать критические данные.

Вот и попробуем Read More »

Posted in Blog, C++, Cryptography, Qt, Ru, Tutorial | Leave a comment

Inferno-rpi-0.6 release

Releasing Inferno-rpi-0.6

Changes:
* Added devi2c
* Added devspi
* Added devgpio (GPIO)
* Minor changes/adjustements
* Boot to kernel-nogui.bin by default. Change config.txt or enter ; wm/wm

Download:
* https://bitbucket.org/infpi/inferno-rpi/downloads/inferno-rpi-0.6.zip

Installation:
1. Download latest zip package from https://bitbucket.org/infpi/inferno-rpi/downloads
2. Pepare SD card with first DOS partition with size less than 250 MB (vfat32 support is not complete)
3. Unzip all files to SD (boot.scr, kernel.bin, … – should in root of SD)
4. Boot Raspberry Pi
5. By default it starts “`styxlisten -A tcp!*!564 export /“`, so you can mount it on other host by “`mount -A tcp!10.0.56.101!564 /n/remote/rpi“` (-A means no auth, IP is for example, see what it got by DHCP)
6. If you boot into want GUI (wm/wm) to be started just edit config.txt and replace kernel-nogui.bin to kernel.bin

Posted in Blog, Inferno OS, Projects, Raspberry Pi, Release | 4 Comments

Inferno-rpi-0.5 release

Releasing Inferno-rpi-0.5

Changes:
* Fixed wrong calculatons of memory pool sizes.
* Support of Pi-1 models with 512MB RAM.
* Update of sources from 9pi project: usbdwc, emmc, etherusb.
* Added uartmini module from 9pi.
* Use Mntgen by default for /n, /n/local, /n/remote
* Boot to kernel-nogui.bin by default. Change config.txt or enter ; wm/wm

Download:
* https://bitbucket.org/infpi/inferno-rpi/downloads/inferno-rpi-0.5.zip

Installation:
1. Download latest zip package from https://bitbucket.org/infpi/inferno-rpi/downloads
2. Pepare SD card with first DOS partition with size less than 250 MB (vfat32 support is not complete)
3. Unzip all files to SD (boot.scr, kernel.bin, … – should in root of SD)
4. Boot Raspberry Pi
5. By default it starts “`styxlisten -A tcp!*!564 export /“`, so you can mount it on other host by “`mount -A tcp!10.0.56.101!564 /n/remote/rpi“` (-A means no auth, IP is for example, see what it got by DHCP)
6. If you boot into want GUI (wm/wm) to be started just edit config.txt and replace kernel-nogui.bin to kernel.bin

Posted in Blog, Inferno OS, Projects, Raspberry Pi, Release | 2 Comments

Wrong size of memory pools – dumb

Occasionally I had a look at /dev/memory:

What I saw there?

; cat /dev/memory
    2282656    14018478     2314496       14149        6246          18    11735810 main
     492768     7009239      499488      110133      106946           4     6516459 heap
       4960    14018478        4960           8           1           1    14013506 image
;

What? I run my Inferno just on 14+7+14 = 33MB memory? (yep and it still runs ok ;) )

The code that define size of memory pools was just copied from other ports:

	ulong nb;
	ulong mpb,hpb,ipb;

	nb = conf.npage*BY2PG;
	mpb = (nb*main_pool_pcnt)/100;
	hpb = (nb*heap_pool_pcnt)/100;
	ipb = (nb*image_pool_pcnt)/100;

	poolsize(mainmem, mpb, 0);
	poolsize(heapmem, hpb, 0);
	poolsize(imagmem, ipb, 0);

See something dumb? :)

240MB memory is not safe to use in calculations because ulong cab be easily overflow to 4GB :)
Yep – 240MB * 50 (%) = 12 000 000 000.

Oops, all previous releases of inferno-rpi have only 33MB RAM. SORRY :)

Surely fixed and coming in next release soon…

Now it is right:

; cat /dev/memory
    2400480    99917824     2434464       14596        6408          18    97517332 main
     498688    49958912      500576      110906      107649           4    49460212 heap
       4960    99917824        4960           8           1           1    99912852 image
; 
Posted in Blog, Inferno OS, Misc, Raspberry Pi, Research | Leave a comment

Thinking about user interfaces, part 3

Part 1
Part 2

Now interesting question, are there user interfaces which based on “verbs”.

Well, I know at least one called drakon-editor: http://drakon-editor.sourceforge.net/

That is extremely powerful tool or a user interface which allow to design algorithms:

Снимок экрана 2015-12-25 в 17.28.59

So you can see, that looks as really totally verb-based user interface. It is very efficient but same time is also limited as do not provide way of defining structures of datas which are processed. So no “object” functionality same time.

Is there a synthesis of these?

Posted in Blog, Ideas, Inferno OS, Research | Leave a comment

Thinking about user interfaces, part 2

Part 1

Now have a look at existing command line interface:

terminal

What really human see on the screen?

A specialist would say that from bottom (from input/cursor) to up the human sees a story of computer operations.

My correction would be that human sees a story of his mental activities shown on the screen. These activities are represented by result of computations, but main point is that what you see on the screen is a storyline of your mental actions :)

In this system user sees nouns (objects) and verbs (actions, commands).

There is interesting effect that computer shows “answers” which are “nouns” while user send “questions” which are close to “verbs”.

That is probably is answer why command line interfaces can be so powerful. A user sees a history of own actions and has to construct next questions to a computer with base of his previous results which he sees on the screen (plus can scroll). A user does not really know state of “reality” – to know the list of files in folder he has to ask a computer for “ls”, but when he gets it printed, it is already in past because time is passing…

But same time console allows to construct mental image of the past actions.

Another example:

commander

Some “commander”.

That is very different concept. Now it is an user iterface that shows available objects of your system of symbolism :).

There is no “history” visible. There is no way to see or construct past states or no way to see actions or verbs.

Naked system of nouns without verbs.

But same time also powerful – user has small limited set of available “verbs”: “copy”, “move”, “delete”, …
User has to keep in his mental universe previous states and construct plan of his future states without a supporting matter.

Interesting that next coils of developing of these interfaces just use same idea.

Windows Explorer:

explorer

File Commander, Mac Finder, thousands of them…

Posted in Blog, Ideas, Inferno OS, Research | 1 Comment

Thinking about user interfaces

Had some time to look into implementation of gui in inferno and take some thoughts.

First maybe about history of graphics user iterfaces and how they brought us to the current situation.

How a computer iteracts to an user?

typewriter

Very first implementations of are just clones of typewriting process – user types on keyboard and same time computer types on paper roll actions. Due to this first commands are pretty small like “ls” “ps” “cd” etc. Also because of that all current shells inherit paradigm of typewriter: user see echo of what he types and between his types he sees “answers” of the computer. Ideal representation of the paradigm is “chatty” – user send “questions” and receive “answers”. That’s all, nothing else. All power of command lines of unix systems is based on idea of “chats” with a computer. More you know about language of “question” then more complicated logic can be launched inside a computer and you looks more powerful to your boss :)

Pretty clear that this paradigm is very limited same time: if “questions” can not cover something in system then you are powerless… Take a look a photoshop user iterface and it is clear that you can not do same with command line with same efforts…

But going deeper, why typewriter idea was in use? That’s only historical reason – we may say nothing else was really same time available that can convert mental matter into storage – from ancient times we have next processes as

1. Drawing – converting mental matter into “images” of physical matter
2. Writing – converting mental matter into “images” of physical matter but using mental system of symbolism.

So our computers inherit systems of our symbolisms…

Let’s have a some example…

I would like to get list of files of root folder. (well, what mean “file”? – some concept of our system of symbolism :), same about a folder). I type “l“, “s“, “enter” on keyboard (why? because it is “synonim” of “list” which is in our system of symbolism means a… list of something :) ). Then on screen I occasinally see few lines of text with names which I can read and translate into mental matter in my conscious where I can operate it with…

So where are these files really exist? (on hard drive?) Hehe, solely only in our mental field (or space) which is structured by our system of symbolism which we have imprinted from school, teached by parents and social environment…

Posted in Blog, Ideas, Inferno OS, Misc, Research | 2 Comments

Inferno-rpi-0.4 release

Releasing Inferno-rpi-0.4

Changes:
* Significant performance improvement due to fixed error in process scheduling/idle
* Boot time is about ONE second :)

Download:
* https://bitbucket.org/infpi/inferno-rpi/downloads/inferno-rpi-0.4.zip

Installation:
1. Download latest zip package from https://bitbucket.org/infpi/inferno-rpi/downloads
2. Pepare SD card with first DOS partition with size less than 250 MB (vfat32 support is not complete)
3. Unzip all files to SD (boot.scr, kernel.bin, … – should in root of SD)
4. Boot Raspberry Pi
5. By default it starts “`styxlisten -A tcp!*!564 export /“`, so you can mount it on other host by “`mount -A tcp!10.0.56.101!564 /n/remote/rpi“` (-A means no auth, IP is for example, see what it got by DHCP)
6. If you do not want GUI (wm/wm) to be started just edit config.txt and replace kernel.bin to kernel-nogui.bin

Posted in Blog, Inferno OS, Raspberry Pi, Release | 1 Comment

Performance

I continue testing the performance.
I made a SD card with 100MB partition and changed config.txt to boot directly kernel.

And WOW!

It looks like the whole OS is loaded up to wm/wm in just 1 sec!

ps. for some reason mice does not work, probably need some adjustments for usb mice driver…

Posted in Blog, Inferno OS, Raspberry Pi, Research, Usb | Leave a comment

Performance, loop 4, solution

I decided to make some simple and temporal solution (but maybe permanent? :) )

In os/port/dis.c in vmachine() have static var indicates when GC was completed last time and start new routine of GC only when at least 500 msecs passed:

void
vmachine(void*)
{
        Prog *r;
        Osenv *o;
        int cycles;
        static ulong lastgcmsec =0;

        startup();

        while(waserror()) {
                if(up->type != Interp)
                        panic("vmachine: non-interp kproc");
                if(up->iprog != nil)
                        acquire();
                if(handler(up->env->errstr) == 0) {
                        propex(currun(), up->env->errstr);
                        progexit();
                }
                up->env = &up->defenv;
        }

        cycles = 0;
        for(;;) {
                if(tready(nil) == 0) {
                        ulong now = TK2MS(MACHP(0)->ticks);
                        if ((now - lastgcmsec) >500 /* || lowmem() */) {
                                strcpy(up->text, "gc");
                                execatidle();
                                lastgcmsec = TK2MS(MACHP(0)->ticks);
                        }
                        strcpy(up->text, "idle");
                        sleep(&isched.irend, tready, 0);
                        strcpy(up->text, "dis");

                }

                if(isched.vmq != nil && (isched.runhd == nil || ++cycles > 2)){
                        iyield();
                        cycles = 0;
                }

                r = isched.runhd;
                if(r != nil) {
                        o = r->osenv;
                        up->env = o;

                        FPrestore(&o->fpu);
                        r->xec(r);
                        FPsave(&o->fpu);

                        if(isched.runhd != nil)
                                if(r == isched.runhd)
                                        if(isched.runhd != isched.runtl) {
                                                isched.runhd = r->link;
                                                r->link = nil;
                                                isched.runtl->link = r;
                                                isched.runtl = r;
                                        }
                        up->env = &up->defenv;
                        if(isched.runhd != nil) {
                                ulong now = TK2MS(MACHP(0)->ticks);
                                if ((now - lastgcmsec) >500 /* || lowmem() */) {
                                        if (up->iprog == nil) {
                                                strcpy(up->text, "gc");
                                                up->type = BusyGC;
                                                pushrun(up->prog);
                                                rungc(isched.head);
                                                up->type = Interp;
                                                delrunq(up->prog);
                                                strcpy(up->text, "dis");
                                                lastgcmsec = TK2MS(MACHP(0)->ticks);
                                        } else
                                                print("up->iprog not nil (%lux)\n", up->iprog);
                                }
                        }
                }
        }
}

That made a trick!

; time math/sieve 1000000 >/dev/null
0.01l 3.13r 3.14t

(3.14 just because it is run on Pi :) )

What is amazing is performance, comparing some 3.3GHz old Core2:

Linux mur 4.1.6-hardened #3 SMP Sun Sep 27 11:44:36 CEST 2015 i686 Intel(R) Core(TM)2 Duo CPU E8600 @ 3.33GHz GenuineIntel GNU/Linux
alex@mur ~/work/pi/bb-inf-rpi/os/rpi $ emu
; time math/sieve 1000000 > /dev/null
0.014l 0.793r 0.807t

New release is coming soon! (let’s just have some little testing)

Posted in Blog, Inferno OS, Raspberry Pi, Research | Leave a comment

Performance, loop 3

When look deeper into tracing what happens when print() is casted

I tried to minimize all codes – copied code of sieve into rpiinit.b, removed everything extra, so whole rpi start does only math/sieve.

Then if press ^T^Tp (Ctrl+T,Ctrl+T,p) I see in console list of processes (not dis progs, but processes):

idleticks:0
f3e148:  1:        interp    0:09.580 pc 0004ef18 New/Ready qpc 00000000 pri 7
f3e5b8:  2:       consdbg    0:00.080 pc 000083e4 kproc/Running qpc 00000000 pri 3
f3ea28:  3:           dis    0:33.250 pc 0007b364 kproc/Ready qpc 00000000 pri 7

Additionally I implemented cpu time counting for processes so you see it in third column.

interp is rpiinit.b which starts sieve, but we see that for some reason a lot of time is spent in another dis process.

It looks like a bug with processes scheduling.

Let’s take a look deeper into the codes – for examples kwrite() syscall (where prints lead into) ends with acquire() so the execution is bypassed to next process.

In next process there is nothing todo (process number 3) so it executes execatidle() (see codes in os/port/dis.c which start garbage collection.

Because math/sieve produces a lot of prints, then every print() syscall forces garbage collection!

Posted in Blog, Inferno OS, Raspberry Pi, Research | Leave a comment

Performance, loop 2

There are still problem with performance, after some experiments i distilled it to next case:

Execution of
time math/sieve 1000000 >/dev/null
takes about 170 secs

Execution of modified math/sieve with commented print() takes only about 3 secs.

So there is a real problem of using syscalls which operates with filesystems. (because even print()/fprint() leads to kwrite() syscall)

Posted in Blog, Inferno OS, Raspberry Pi, Research | Leave a comment

Problem with dossrv

Just made new attempt with new SD card and found that with defaults: 4GB dos formatted (full sd) is not mounted during boot. With booting kernel-nogui.img I got a console and had a look.

Looks like dossrv has problems with supporting large partitions.

So for now if you would like to boot 0.3 release please make small first 100MB dos partition and write distro files there.

I may need to have a look at dossrv fault later.

Posted in Blog, Inferno OS, Raspberry Pi | 1 Comment

Inferno-rpi-0.3 release

Releasing Inferno-rpi-0.3

Changes:
* Enabled JIT
* Included recent updated of Inferno-Os
* Memory split 240/16
* devcons is added

Download:
* https://bitbucket.org/infpi/inferno-rpi/downloads/inferno-rpi-0.3.zip

Installation:
1. Download latest zip package from https://bitbucket.org/infpi/inferno-rpi/downloads
2. Pepare SD card with just one DOS partition (just format into the dos)
3. Unzip all files to SD (boot.scr, kernel.bin, … – should in root of SD)
4. Boot Raspberry Pi
5. By default it starts “`styxlisten -A tcp!*!564 export /“`, so you can mount it on other host by “`mount -A tcp!10.0.56.101!564 /n/remote/rpi“` (-A means no auth, IP is for example, see what it got by DHCP)
6. If you do not want GUI (wm/wm) to be started just edit config.txt and replace kernel.bin to kernel-nogui.bin

Posted in Blog, Inferno OS, Projects, Raspberry Pi, Release | 2 Comments

JIT is ON

My research about JIT in inferno-rpi is ended. The cause was obvious but until you does not know about and search through sources, doing debugging, tracing, experimenting – you would not know what it is.

So it is simple – DIS op codes are compiled into ARM machine routines and when compilation is finished it bypasses CPU execution to the address where ARM codes are now. But on the SoC, the instructions cache is not informed automatically that codes about to run are probably in write buffers and not in sync with RAM.

It requires to drain write buffers and invalidate data cache with cachedwbinvse(pos,n) and then invalidate instructions cache with cacheiinvse(pos,n) which I implemented. Those two calls are placed into segflush() which is called by compiler on the end of compilation before bypassing execution there.

JIT is ON now.

Posted in Blog, Inferno OS, Raspberry Pi, Research | Leave a comment

JIT is off

I decided to have a look at the problem of speed – it is really visible that inferno os on raspberry is slow. My fisrt opinion was about probably disabled caches, but I was wrong – it works fine.

After keeping searching I realized that Inferno-Rpi is actually has JIT off. Oops!

That is controlled by “int cflag =0” in rpi config, which was copied from I guess “ipiaq” config or similar. So I never had doubt that dis runs in the interpretation mode.

But when cflag was set to “1”, then it just crashes… Mabt exception on Arm, so looks like generated code is probably does not fit something or…

Anyway need to do some further research.


[Fdisk] Broken: "sys: trap: fault pc=0106cf90"

Posted in Blog, Inferno OS, Raspberry Pi, Research | Leave a comment

Inferno-Rpi: project moved

Due to the closure of google code, the project is now moved to: https://bitbucket.org/infpi/inferno-rpi

Also added some minor changes and merged with latest inferno-os codebase changes. So returning a little to the project activity and think to keep the project based on dos partition which will be very simple for demo purposes.

Also think to keep in sync repo on github: https://github.com/yshurik/inferno-rpi

Posted in Blog, Embedding, Inferno OS, Raspberry Pi | Leave a comment