23 September, 2010

270 days of summers

It became a tradition, that every summer dramatically changes my life.

In 2008 my engineering skills were too low for real development, but I had been accepted into Google Summer of Code and it changed my vision of what development and engineering are. I understood that programming languages are mostly like human one: most important is what you say and not just speaking style. You can know language well, but you can have nothing to say.

At the same time I had very strong family problems: cancer started to kill my lovely granny, who was my best friend and mentor all my life. Now I see, all that pain made me much stronger and I studied a lesson, that every day is important in our life and nobody knows what can happen tomorrow.

Nothing as important as people who love us and whom we love, and it's stupid to waste the time fighting for good reputation and status in "gangs" you don't respect and who never will understand you. The only thing you should do is to build your own word, but not to try to change our big blue sphere whining why most part of people have forgotten what is love, friendship, honor and adherence to the principles. Lieutenant colonel Dmitry Razymovskiy (Vympel, Russian FSB/FSS) sayed: "If a person is not your friend, he is not there for you, if an enemy - he should not exist at all".

To the beginning of summer 2009 I was fully broken: granny just died, I failed to cancel academical vacation and to start next course in university (started the same I had before vocation). The only good thing I had was an offer from Professor Tanenbaum to hack on MINIX 3. It was the thing which helped me to survive after everything that happened. My two projects I've done for MINIX 3 (FPU hardware support and ext2 file server), the team (especially Ben Gras, Thomas Veerman, David van Moolenbroek — the people on whom I want to be like) protected me from the thoughts about past. I enjoyed implementing interesting things (ext2 project was very challenging project for me). It's unforgettable time.

Summer 2010. Just finished ext2, was waiting for a new project from Prof. Tanenbaum.
During summer I met two girls, who gave me good lessons:

1. It's OK if somebody loves you and you don't — it's just a normal situation and the only thing to take care about is not to hurt another one. Good thing is that I was the person who didn't love. This helps when you get into situation which is vice verse: then you don't say "Why???", you just say "Damn!" :-)

2. When you have a real love, the whole courting phase is not the same as seduction of a girl you want, but it's a part of romantic relationships, a very pleasant part which full of spiritual experiences, dreaming, suffering and joys. When you have a true love you become : not only the result is important, but all the "technology" in general. You don't fall into "I want just sex with this pretty girl", wanting her means wanting to know what kind of person she is, what she's doing every day. You need, no, you have to know her plans, thoughts and dreams.

At the same time I was "studying" second lesson, I got an offer from an IT corporation which does data storage. And I had to do a tough choice: freelancing on Prof. Tanenbaum or full day work in a good US company. Regular financial problems and at some point that girl forced me to leave MINIX 3 and start working at the office. I miss MINIX 3 and the team, but I'm happy: not only finances fixed, but everyday I meet interesting people whom I respect for their engineering skills and high technical level. Office is better than mailing lists and IRC. I'm working three weeks already and already hacking (Yai, bash scripting!). The only thing which I'm worried about is feeling, that I can do my job much better than now and to have my day better organized.

What was this all about? Life is an amazing thing and it worth living. We have to do choices very often, but many random events affect our decisions. A big mistake some geeks do is trying to find manual to factorize everything and to get full control: you can't, stop searching that mythical man pages and start living.
Don't learn to live, live to learn! :-) Build your own world with your own community and don't fuck with the rest.

P.S. From summer 2009 I have two unclosed issues: I want AST to sign me a book and to to treat Ben drinking. Well it seems I have to travel to Amsterdam :D

Born again

Few interesting things I've recently discovered:

bar ()
    exit 1

foo ()
    [[ $? -ne 0 ]] && echo "bar() failed"
    # Now try local
    local var=`bar`
    [[ $? -ne 0 ]] && echo "bar() failed again"

You will not see "bar() failed again", as you can expect. Second time "$?" will be an exit status of local like I was explained by much more experienced engineer.

Another unexpected thing is about re in grep:
echo -e "foobar" | grep "^\(foo\)\{0,1\}bar"
echo -e "foobar" | grep "^\(foo\)\{0,0\}bar"
Explanation is simple: {0, 0} is zero-length substring, which means anything before "bar". You can't achieve equivalent of "-v" flag with {0}.

21 September, 2010

MINIX 3: pre-release of 3.1.8 available

MINIX  3.1.8 includes my ext2 implementation :-)
Unfortunately it seems that I will not be able to hack on MINIX 3 in the nearest future.

Official release information:
minix3: pre-release of 3.1.8 available at http://www.minix3.org/download/ , new features at: http://wiki.minix3.org/en/MinixReleases!

07 April, 2010

Basic ext2 server for MINIX 3 is available for testing

I've just pushed my master branch to gitorious repository, so anybody can pull it and use my ext2 server.
But note: it's not yet finished and is still under development. I noticed bugs with long and ugly names only, but anyway for now use it on your own risk. Mounting ext2/ext3 in read-only mode is safe.

Disclaimer: I'm not part of VU team and at this step code wasn't verified by them (HEAD is under review by Thomas Veerman now and results will be available later). This project is supposed to be merged with MINIX 3 trunk later if everything is ok.

30 March, 2010

On the dangers of drugs

First I smiled, but at the end I was trying to сlose my mouth in surprise...

29 March, 2010

Most beatiful bug I ever had

While testing my ext2 MINIX 3 server I found a bug which caused problems on file systems with 1024 block size. I used following work flow: download about 1 Gb of different files (either wget or using HGFS/MFS), remove some files and download some more. Then I checked md5sums. Everything was fine. But in Linux e2fsck started to enlarge filesizes of files greater than 64 Mb. The only thing that could differ from file systems with greater block sizes was ranges of indirect blocks (singe, double and triple) and most wonderful thing I discovered is that I had problem with double indirection, which was fine with another block sizes. Correct md5sums pushed me in the wrong direction...
So after some time I discovered that I had to check md5sum in Linux before running e2fsck: it differed from md5sum I got in MINIX! After running cmp I noticed the problem was in last double indirect addressed block, which was really really really strange (function wich maps blocks to positions was very well tested).
And the reason was in pow() function implemented in MINIX 3 (during tests I used python prototype and then gcc)... Instead of shifting or multiplication (block_size^{2,3}) I used pow()... What a bad idea it was! Triple indirect blocks should start at 65804 block and in MINIX same code produced 65803 which was last double indirect addressed block. So I just had working implementation of ext2 incompatible with all another ext2 implementations :D

11 March, 2010

Evolution of one simple function (ext2_max_size)

For a while I've been working on ext2 fs implementation for Minix 3 (ext2 server in Minix terms). I've already implemented ext2 server which can read and write. One of functions required by implementation is ext2_max_size which calculate max file size for ext2/ext3 fs.
Here is a function from linux (with my comments):

 *  linux/fs/ext2/super.c
 * Copyright (C) 1992, 1993, 1994, 1995
 * Remy Card (card@masi.ibp.fr)
 * Laboratoire MASI - Institut Blaise Pascal
 * Universite Pierre et Marie Curie (Paris VI)
 *  from
 *  linux/fs/minix/inode.c
 *  Copyright (C) 1991, 1992  Linus Torvalds
 *  Big-endian to little-endian byte-swapping/bitmaps by
 *        David S. Miller (davem@caip.rutgers.edu), 1995

 * Maximal file size.  There is a direct, and {,double-,triple-}indirect
 * block limit, and also a limit of (2^32 - 1) 512-byte sectors in i_blocks.
 * We need to be 1 filesystem block less than the 2^32 sector limit.
static loff_t ext2_max_size(int bits)
        /* eivanov: bits = 10 + log2(block_size/1024),
         * note that 2^10 is 1024, which is minimal block_size on ext2,
        loff_t res = EXT2_NDIR_BLOCKS;
        int meta_blocks;
        loff_t upper_limit;

        /* This is calculated to be the largest file size for a
         * dense, file such that the total number of
         * sectors in the file, including data and all indirect blocks,
         * does not exceed 2^32 -1
         * __u32 i_blocks representing the total number of
         * 512 bytes blocks of the file
        upper_limit = (1LL << 32) - 1;

        /* total blocks in file system block size */
        /* eivanov: same as "upper_limit /= (block_size/512)" */
        upper_limit >>= (bits - 9);

        /* indirect blocks */
        meta_blocks = 1;
        /* double indirect blocks */
        meta_blocks += 1 + (1LL << (bits-2));
        /* tripple indirect blocks */
        meta_blocks += 1 + (1LL << (bits-2)) + (1LL << (2*(bits-2)));

        upper_limit -= meta_blocks;
        upper_limit <<= bits; /* upper_limit in bytes */

        res += 1LL << (bits-2);
        res += 1LL << (2*(bits-2));
        res += 1LL << (3*(bits-2)); /* eivanov: total blocks addressed by inode */
        res <<= bits; /* eivanov: res in bytes */
        if (res > upper_limit)
                res = upper_limit;

        if (res > MAX_LFS_FILESIZE)
                res = MAX_LFS_FILESIZE;

        return res;
This function can work with any block_size, but the only supported block_sizes are 1024, 2048, 4096 and on rare platforms 8096. Thus it only calculates constants. I can recall any reason to calculate constants instead of using literals.
Here what I wrote while I was reading linux' function (used arithmetics instead of shifting):

long long ext2_max_size2(int block_size)
    /* Note, that this one takes block_size instead of bits */
  long addr_in_block = block_size/4; /* 4 bytes per addr, long for further arithmetic */
  long sectors_in_block = block_size/512;
  long meta_blocks; /* single, double and triple indirect blocks */
  long long out_range_s; /* max blocks addressed by inode */
  unsigned long long max_bytes;
  unsigned long long upper_limit;

  /* 1 indirect block, 1 + addr_in_block dindirect and 1 + addr_in_block +
   * + addr_in_block*addr_in_block triple indirect blocks */
  meta_blocks = 2*addr_in_block + addr_in_block*addr_in_block + 3;
  out_range_s = 12 + addr_in_block + pow(addr_in_block, 2) + pow(addr_in_block, 3);
  max_bytes = out_range_s * block_size;

  upper_limit = (1LL << 32) - 1; /* max 512-byte blocks by i_blocks */
  upper_limit /= sectors_in_block; /* total block_size blocks */
  upper_limit -= meta_blocks; /* total data blocks */
  upper_limit *= (long long)block_size; /* max size in bytes */

  if (max_bytes > upper_limit)
      max_bytes = upper_limit;

  return max_bytes;

IMHO it's much more readable. Probably compiler will not gnerate shifting instructions, but this function is called just once, when fs is mounted, so don't claim on performance.

Then I came to decision use following function (similar):

unsigned long ext2_max_size2(int block_size)
        case 1024: return 67383296L;
        case 2048: return 537944064L;
        case 4096: return 4286562304U;
        /* add default panic, when move to kernel server */
Also there is a small pitfall: these constants also depend on EXT2_NDIR_BLOCKS, but the code listed above doesn't use it. So ideal variant is to check if EXT2_NDIR_BLOCKS is the same as was used in calculations (99.9 that it is, since changing it will break compatibility with older on-disk filesystems) and recalculate if it was changed.
Would it be the fastest? Sure! Simplest? Of course :) The only missing thing is missing 8096 block size, since it's used on some rare architecture (don't remember name) which will not be supported by Minix 3 (x86 and arm/x86-64 in plans). Also there is a small pitfall: these constants also depend on EXT2_NDIR_BLOCKS, but the code listed above doesn't use it. So ideal variant is to check if EXT2_NDIR_BLOCKS is the same as was used in calculations (99.9 that it is, since changing it will break compatibility with older on-disk filesystems) and recalculate if it was changed.