Wednesday, December 29, 2010

Disk Failure, Raid Corruption and CRCs

This week is started with a raid corruption due to a disk failure. Disk has continued to work without notifying anyone about the corruption, but this is somehow acceptable. The inacceptable thing is that the file-system is not aware about its data state. The "Old File-Systems" are not interested in user data and even with journaling, user data is not  a priority.

As a Spare-Time File-System Developer, is really funny saying "With my File-System, This failure would not have happened!"

Simple Solution: B-Tree and CRCs
A really simple way to solve this problem is adding CRC to user data, or better (from file-system point of view) adding a CRC on every block. If the file-system is entirely based on B-Tree (when I say B-Tree, I mean B*Tree or B+Tree) you can simple add CRC for the block in the node header, and CRC for the child in the blocks pointer.

Excluding from a moment the super-block and other things... You start reading the root of the tree (1st block), if node crc check fail there's something wrong with your disk-read (or maybe your memory, but this is less probable). When you start traversing the tree the check is even better and "secure".

Checking the CRC on the block read is good, but having the CRC stored in a different location, and read at a different time is even better.

Storing CRC of the child node within the pointer gives you the ability to do a double integrity check. When data becomes larger and cannot be stored in a tree node, you can do the same thing with the extents (Pointers and CRC).

Another maybe more "intrusive" solution is storing a CRC for every N bytes of data, but I think that this more acceptable for a user-space "crc-fs" implementation (This approach is implemented in Hadoop's ChecksumFileSystem class).

Yesterday night I've implemented a quick and dirty B+Tree, it's not tuned for speed but for a didactic view. It has a couple of nice features like Pointers with CRC and Variable Length nodes to be able to compress nodes on disk. You can find the source code on my github repository (B+Tree Code).

Saturday, November 6, 2010

Cocoa: Black Window Titlebar

Starting with Quicktime X and now with Facetime, Apple has introduced a new black ui titlebar. There's no NS component at the moment or any flag of NSWindow, so I've decided to throw away ten minutes to write my own black titlebar.
I've created a NSWindow class (BlackWindow.h/BlackWindow.m) that initializes a window without borders (styleMask NSBorderlessWindowMask) and I've created a NSView that draws the titlebar (BlackWindowTitleView.h/BlackWindowTitleView.m).
The titlebar redraws itself when some changes are applied to the window. With key value observing for title, document edited, ... and NSNotificationCenter for KeyNotifications the titlebar knows what to do.

Source code can be found on my GitHub under blog-code/MacBlackWindow.
git clone https://github.com/matteobertozzi/blog-code.git

Friday, October 15, 2010

Python: Inverted Index for dummies

An Inverted Index is an index data structure storing a mapping from content, such as words or numbers, to its document locations and is generally used to allow fast full text searches.



The first step of Inverted Index creation is Document Processing In our case is word_index() that consist of word_split(), normalization and the deletion of stop words ("the", "then", "that"...).
def word_split(text):
    word_list = []
    wcurrent = []
    windex = None

    for i, c in enumerate(text):
        if c.isalnum():
            wcurrent.append(c)
            windex = i
        elif wcurrent:
            word = u''.join(wcurrent)
            word_list.append((windex - len(word) + 1, word))
            wcurrent = []

    if wcurrent:
        word = u''.join(wcurrent)
        word_list.append((windex - len(word) + 1, word))

    return word_list
word_split() is quite a long function that does a really simple job split words. You can rewrite it with just one line using something like re.split('\W+', text).
def words_cleanup(words):
    cleaned_words = []
    for index, word in words:
        if len(word) < _WORD_MIN_LENGTH or word in _STOP_WORDS:
            continue
        cleaned_words.append((index, word))
    return cleaned_words

def words_normalize(words):
    normalized_words = []
    for index, word in words:
        wnormalized = word.lower()
        normalized_words.append((index, wnormalized))
    return normalized_words
Cleanup and Normalize are just to function filters to apply after word_split(). In this case cleanup remove the stopwords (frozenset of strings) and normalize convert word in lower case. But you can do something more like removing accents, transform to singular or something else.
def word_index(text):
    words = word_split(text)
    words = words_normalize(words)
    words = words_cleanup(words)
    return words
word_index() is just an helper, take an input text and does all the word splitting/normalization job and the result is a list of tuple that contains position and word. [(1, u'niners'), (13, u'coach')].
def inverted_index(text):
    inverted = {}

    for index, word in word_index(text):
        locations = inverted.setdefault(word, [])
        locations.append(index)

    return inverted
Finally we've our invertex_index() method that take a text as input and returns a dictionary with words as keys and locations (position of the words in the document) as values.
def inverted_index_add(inverted, doc_id, doc_index):
    for word, locations in doc_index.iteritems():
        indices = inverted.setdefault(word, {})
        indices[doc_id] = locations
    return inverted
The Previous method, inverted_index(), returns a dictionary with just the information for the specified document. So inverted_index_add() add Document's inverted index to a Multi-Document Inverted Index. Here we've words that are keys of the dictionary and values are dictionary with doc_id as key and document location as values. {'week':{'doc2': [149], 'doc1': [179, 187]}}.
def search(inverted, query):
    words = [word for _, word in word_index(query) if word in inverted]
    results = [set(inverted[word].keys()) for word in words]
    return reduce(lambda x, y: x & y, results) if results else []
Now that we've the inverted index, we're able to do queries on it. The function above takes a Multi-Document Inverted index and a query, and returns the set of documents that contains all the words that you've searched.

Obviously to make a serious search function you need to add ranking, phrase matches, stemming and other features of full-text search. And you need to write your dictionary using an on disk btree. But this is a basis example, of how to build an inverted index.

Source code can be found on my GitHub repository under py-inverted-index:
git clone http://github.com/matteobertozzi/blog-code.git

Saturday, October 9, 2010

Unsigned Int of specified bit length

Finally I've added 128+ bit support to RaleighFS Table Object Row Index. I don't need much operation on indices only inc, dec and compare, but I've implemented other couple of methods (add, and, or, xor) and now there's a mini uintX library available at GitHub.

...
uint8_t index[16];    // 128bit unsigned integer

uintx_init(index, 128U);   // Initialize 128bit index to zero.

uintx_inc(index, 128U);    // Increment Index (Now is One)
uintx_dec(index, 128U);    // Decrement Index (Now is Zero)

uintx_from_u64(index, 128U, 8192U);    // Now index is 8192

uintx_add64(index, 128U, 5U);          // Add 5 to index

uintx_compare(index, 128U, 8197U);     // Return 0
uintx_compare(index, 128U, 9197U);     // Return -1
uintx_compare(index, 128U, 0U);        // Return 1
...

The API is quite simple pass your object (uint8_t vector) and its bit size (uint8_t[16] is 128bit) and other args needed to the method. Of course you can replace 128 with 256, 512 or everything else.

The source code can be found at my GitHub in the uintx folder:
http://github.com/matteobertozzi/carthage.git

Saturday, September 25, 2010

iOS4: Core Motion Viewer

I'm playing with Core Motion (Accelerometer and Gyroscope) of my new iPod Touch 4th. And I've written a simple app to look at the values of Motion Sensors. Code is not so much interesting, but it an useful app to check motion values.

Sunday, September 19, 2010

Python: NetStack/CoreAsync

Today I've added to my GitHub Respositories NetStack/CoreAsync a python "package" (It's much more a bunch of utility classes) that allows you to code in async/parallel way, that I use to build my networking apps.
def concurrent_func(text):
    for i in range(5):
        print text, 'STEP', i
        yield

coreasync.dispatch_concurrent(lambda: concurrent_func("Context 1"))
coreasync.dispatch_concurrent(lambda: concurrent_func("Context 2"))
coreasync.runloop()

Package contains a small Async HTTP Server implementation that you can easily use:
def handle_response(socket, addr, request, headers, body):
   yield socket.send(...)

def handle_error(socket, addr, error):
   yield socket.send(...)

coreasync.httpserver.httpServerLoop(HOST, PORT, handle_response, handle_error)
print 'HTTP Server is Running on', HOST, PORT
coreasync.runloop()

You can find Source Code and Examples at GitHub:
git clone http://github.com/matteobertozzi/netstack-coreasync.git

Sunday, August 15, 2010

Qt4 Http Request Parser

Qt 4.4 introduces QNetworkRequest and QNetworkAccessManager to help you with your HTTP client request. But if you want parse an HTTP Request, because you're writing an HTTP server, it seems that there's nothing already done (comment here, if I've missed it).

So, this morning I've written a little class that help you with HTTP Request parse:

  • static HttpRequest fromData (const QByteArray& data);
  • static HttpRequest fromStream (QIODevice *buffer);

There's a couple of method that you can use to parse your request data, and some others method to retrieve headers, method type, url and body data.

Qt is used only for QHash, QByteArray and QIODevice classes, you've to implement all the "socket" logic, to handle your client request and response.

The Source code is available here: Qt4 Http Request Parser Source Code.

Friday, August 13, 2010

Self Contained C Data Structures and Utils Repository

I've rewritten a couple of data structure and utils (C lang) that I use for my RaleighFS Project, and I've released it at github under BSD License.

At the moment there are some data structures and helper functions:
  • Memory Pool - Simple Memory Allocator.
  • Memory Utils - memcpy(), memset(), memcmp(), memswap() with some variants.
  • Memory Block - copy-on-write block.
  • Hashed Containers: Hashtable, Set, Bag.
  • Queue - FIFO/Circular Queue.
  • Cache - LRU/MRU Cache.
  • WorkQueue - Lightweight pthread workqueue.
  • Sort/Merge functions.

Every "object" is self contained, you can grab the "hashtable.c/hashtable.h" file to be ready to use the hashtable, no other dependence is required. And if data structure require a malloc() you can specify your own allocator during object initialization.

Saturday, July 24, 2010

iPhone/Qt: UDP Voice using AudioQueue/QAudioOutput

Qt 4.6 Introduces QtMultimedia with support for raw audio input/output, while Mac OS X and iPhone OS has well known CoreAudio/AudioQueue from a long time.

This example show how to implement a really rudimentary VOIP between an iOS (iPhone/iPod Touch/iPad) and a Desktop (using Qt). To simplify the example is just unidirectional iOS to Qt, because doing Qt to iOS part is just the specular code.

The idea is very simple, Fetch the sample data from the microphone, and send over UDP. No compression no packet number just send raw data in simple way as possible.

On iOS we've AudioQueueNewInput() that creates a new recording audio queue object, and AudioQueueNewOutput() that creates a new playback audio queue object.

The specular Qt 4.6+ classes are QAudioInput class that provides an interface for receiving audio data from an audio input device, and QAudioOutput class that provides an interface for sending audio data to an audio output device. To handle audio samples we can easily wrap QIODevice read() and write() calls.

The source code is really easy. iOS code contains AudioRecorder.h/AudioRecorder.m that is a C code that wrap AudioQueue Input to record a stream, with a callback handler to intercept packet data. The Qt4 Source code contains just  a QIODevice Wrapper that read from UDP and prepare for QAudioOutputStream. It's really really simple, but gives you an idea.

The Source code is available here, and contains both Qt 4.6+ and iOS sources: iPhone/Qt UDP Voice Source Code.

Note: Due to a QTBUG-8878 we cannot use 8, 16, 24 KHz Frequency. Will be fixed in Qt 4.6.4.

Saturday, July 10, 2010

RaleighFS is moving to Flash Disks

No, this is not going to happen for a couple of years, I love spinning disk, because file-system can really do the difference in term of performance.

But… This week I've talked a bit with my colleague batt, that is working on some new features of his BattFS available on BeRTOS. And I've discovered that flash disk are challenging too, especially on embedded devices where you cannot use large cache due to ram limitation.

What changes, on flash, from a traditional File-System? First of all due to limited rewrite cycle of a block, you cannot modify a block in place (Append-Only Data Structure needed). Append-Only Index is not a problem, but Traditional file-system heavily rely on a fixed location super-block that contains the root pointer, and append-only tree root changes every time, so super-block need to be re-writed.

The first solution that RaleighFS can quickly implement is to write a new super-block each flush. In this way each flush (or transaction) can be easily identified. But how can I reach the last super-block and what is the last super-block?



The Worst case is to scan the whole disk to find the super-block "magic" number in block header.

But what we can do is to add some information to the super-block
  • Super-Block Id
  • Next Super-Block Id
  • Next Super-Block Location

In this way on each flush we "predict" what is the location of the next super-block, and we give it an unique id just to be sure to identify the next one. In this way we can avoid to scan the whole disk but just a few Mb (flush size) and then we can easily jump to the next super-block until the super-block next location isn't valid.

Block allocation is just a "round-robin" allocation in this way we're able to keep aligned "every" block erase cycle, and this solve the super-block location problem.



What about the tree? Tree is the common B*Tree of RaleighFS with a few changes:
  • Modified leaf node is allocated/writed in a new place
  • Root and Twigs Nodes are rewritten only if keys changes.

Wait wait, how we can reach the new leaf node? To avoid large Twigs rewrite we keep a small BTree (high fanout) that maps old leafs block numbers with the new ones. Free blocks can be stored on disk or better due to 0-seek time we can just check all the tree pointers to see what's allocated.

I'm not really convinced about the map BTree, but seems to solve the "large update" of value modification in key/value storage case… This is just a fast "port" of current RaleighFS to SSD but maybe something really different can be used...

Thursday, July 8, 2010

PyQt4: Electronic Oscillator

An electronic oscillator is an electronic circuit that produces a repetitive electronic signal: sine wave, square wave and any other repetitive mathematical function.

So, why an Oscillator? Because, I'm currently looking at Audio, and Audio Effects (Distortion, Chorus, Delay, Flange, Reverb, ...) and the sound is basically a wave with a certain frequency.

How can you visualize your effect function? I've created this one above using Python and PyQt4. Less than 200 lines of code. Including the Oscillator class with 5 types of wave (ok, not so difficult).

You can find the source code here: PyQt4 Electronic Oscillator Source Code.

Saturday, May 8, 2010

PyCon4: Python FUSE Talk Slide and Source Code

Talk is over, Slide and source code can be found on my develer tech blog http://mbertozzi.develer.com


Slide PDF is also available here PythonFuse.pdf, and examples git respository here:  Python FUSE Examples Web Git Repository.

Sunday, April 18, 2010

Qt Animation Framework Example

Today I've finally written my first example with the Qt Animation Framework (Qt 4.6).

The animation framework aims to provide an easy way for creating animated and smooth GUI's. By animating Qt properties, the framework provides great freedom for animating widgets and other QObjects.

The examples is really simple, few lines of code. And the Qt Animation Framework does all the magic under the hood. Just assign the Start and the End Value for the specified property and the interpolator does the rest.

YouTube video is available here: Qt Animation Example Video and you can find the Source Code here: Example Source Code.

Sunday, March 28, 2010

Cocoa: Draw your Shelf!

Back a bit to play with cocoa, new file-systems need new metaphor for desktop, Shelves? Below you can find a simple draw code, that you can port easily in qt or other library that have a good painter.

The code is really simple, just draw a rectangle and a path to give a perspective effect.
- (void)drawRect:(NSRect)frameRect {
  NSGradient *gradient;
  NSColor *startColor;
  NSColor *endColor;
  NSBezierPath *path;

  [NSGraphicsContext saveGraphicsState];

  CGFloat height = frameRect.size.height - 1.0f;
  CGFloat width = frameRect.size.width - 1.0f;
  CGFloat pcp = 10.0f;
  CGFloat sh = 10.0f;     /* shelf Height */

  path = [NSBezierPath bezierPath];
  [path setLineJoinStyle:NSRoundLineJoinStyle];
  [path moveToPoint:NSMakePoint(0.0f, sh)];
  [path lineToPoint:NSMakePoint(width, sh)];
  [path lineToPoint:NSMakePoint(width - pcp, height)];
  [path lineToPoint:NSMakePoint(pcp, height)];
  [path fill];

  startColor = [NSColor colorWithCalibratedRed:0.85f
                        green:0.66f blue:0.45f alpha:1.0f];
  endColor = [NSColor colorWithCalibratedRed:0.78f
                      green:0.61f blue:0.42f alpha:1.0f];
  gradient = [[NSGradient alloc] initWithStartingColor:startColor
                          endingColor:endColor];
  [gradient drawInBezierPath:path angle:90.0f];
  [gradient release];

  path = [NSBezierPath bezierPathWithRect:NSMakeRect(0.0f, 0.0f, width, sh)];
  startColor = [NSColor colorWithCalibratedRed:0.29f
                        green:0.16f blue:0.04f alpha:1.0f];
  endColor = [NSColor colorWithCalibratedRed:0.48f
                      green:0.30f blue:0.16f alpha:1.0f];
  gradient = [[NSGradient alloc] initWithStartingColor:startColor
                                  endingColor:endColor];
  [gradient drawInBezierPath:path angle:90.0f];
  [gradient release];

  [NSGraphicsContext restoreGraphicsState];
}

Saturday, January 30, 2010

PyQt4 Schema Script

I've received a couple of emails asking me what I use to draw various graphs and schema that I post on this blog. And the obviously answer is QPainter! I've a small PyQt script that does the easy things but the more difficult one is coded every time...


The script is really simple, it take an xml input and just draw the few items that can recognize. You can use RGBA colors and you can draw linee-paths, like in the image above. The XML looks like this one:



<!-- Green Rect -->
<item type='rectangle'
x='130' y='140' width='140' height='60' 
border='1/0x98b954' 
color='0xf4ffe4/0xdbfdab' />

<text x='130' y='140' width='140' height='60'
color='0x000000' font='Arial'
size='12' bold='false' italic='true'>
I'm just a Test!
</text>        

<!-- Links Line -->
<line path='70,120;70,170;130,170' />



I know that it's a stupid thing and making xml seems to be a long job, but this is what I need at the moment, maybe in the future this script will get a WYSIWYG ui but at this time is just a simple script that generate an image :)

The source code with the above example is available here: PyQt4 Schema Script.

Directories and File-System, RaleighFS Way!

When you talk about a new file-system to someone, one of the first question that you will hear is "It will suffer from directory unbalancing" or "How performs with larger directories".

Ext3 seems to have spread the fear of large directory, but What is a directory? and what large directories mean?

When you design a File-System you've to decide what is your target/end-user. Don't try to design your file-system for everyone, but just for one.

So, what's your focus? Be the fastest file-system for continuous 'ls' (Directory traversing)?

My idea and RaleighFS idea, is that File-System is just a "Big Hashtable" with some useful information, where you ask for an item 'x' and you'll receive it's data, and metadata. Following this idea, what is a directory? It's just a name-container that allows user to keep track of his items. At this point, what is the best way to represent Directory?

Directory is just another item in the FS, like your mp3, c source file, and all the other stuff.


When you're a high-level developer, sometimes you forget how the low-level works, in this case the File-System. The FS has blocks when you remove something from the begin/mid of a file you shift back all the rest and you rewrite the entire file to avoid this you can intelligently pack your data based on the "block-data size" of the file system. (Block data size is not the block size, maybe the file-system add its own block header to your data).

The above picture shows the RaleighFS Directory Block data structure. There's a small block header that say how much of space are free in this block and there're directory items that are simply 2-field struct, 1 byte name size and N chars for the name.
block_size = 8192 byte
block_head = 12 byte
dir_head = 2 byte
avg_dir_item_size = 1byte + 15 byte (avg name size)
(block_size - block_head - dir_head) / avg_dir_item_size = 511 entries in one block

In a few blocks you can handle large amount of files, and the remove operation are really quick. Just find your item, move back just your "block" friends and decrease the Directory Header free space. In this way you don't have to rewrite all the item but just one or few blocks of it.

Remember, in RaleighFS, directory is just a name-container that allows user to keep track of his items (ls /home/) and on disk directory is just a file there's no unbalance. Every item is looked-up in a  O(1) Time, like traditional Hashtables.

Saturday, January 16, 2010

Qt4 Image Crop Item

Just a quick break from Math, File-System and Data Structure (I'm overly busy). The example below is a simple QGraphicsItem, that allow the user to select an area on the screen, like the "crop tool" that you can see in every Image Editor. The source code is very simple, just paint() and moveEvent() handlers.


The source code is available here: Qt4 Image Crop Item Source Code.

Saturday, January 9, 2010

Base Raleigh Library is out

In these days I've rewritten parts of my Raleigh Library, that I use for my work-in-progress file-system (RaleighFS). The Library provides the basic Abstraction mechanism for read/write data from devices, client-server communication, threading and various data structures like Hashtable, Sets, In-Memory Stream (Chunk), Red-Black Tree, B*Tree and other things.

I've published the base source code, with BSD license, at google code (http://code.google.com/p/raleigh). You can download it using Mercurial.

hg clone https://raleigh.googlecode.com/hg/ raleigh


The usage is very simple, and the source code contains Test Cases and Examples that shows how to use all the "classes". For more information feel free to send me a mail.