Several filesystem related trees (0)

Coly has given an intro to the B_tree algorithm in Nov.'s linuxfb.org seminar. Here I'm going to extend his introduction to a brief overview of several file system related trees.

Following is a list of trees I plan to write about(might be extended). I hope I can finish the list before the end of 2009 :)

1. B_tree
2. b+tree
3. Htree
4. Dancing tree
5. Hash tree
6. Tiger tree
7. rb-tree

glibc malloc implementation

I've been asked several time in interviews how libc implements malloc function. So here I give the a simple summary.

First, I'd like to copy some simple malloc implementation found from Internet.
simple explaintion of malloc:

struct mem_control_block {
 int is_available;
 int size;
}; 

1. If our allocator has not been initialized, initialize it.
2. Add sizeof(struct mem_control_block) to the size requested.
3. start at managed_memory_start.
4. Are we at last_valid address?
5. If we are:
A. We didn't find any existing space that was large enough
-- ask the operating system for more and return that.
6. Otherwise:
A. Is the current space available (check is_available from
the mem_control_block)?
B. If it is:
i) Is it large enough (check "size" from the mem_control_block)?
ii) If so:
a. Mark it as unavailable
b. Move past mem_control_block and return the pointer
iii) Otherwise:
a. Move forward "size" bytes
b. Go back go step 4
C. Otherwise:
i) Move forward "size" bytes
ii) Go back to step 4

However, the real-world in libc in much more complicated and thus much more efficient.
Since 2.3 release GNU C library (glibc) uses a modified ptmalloc2, based on "Doug Lea's Malloc" (dlmalloc), which is a lock free implementation.

Quoting glibc/malloc/malloc.c:

  The main properties of the algorithms are:
  * For large (>= 512 bytes) requests, it is a pure best-fit allocator,
    with ties normally decided via FIFO (i.e. least recently used).
  * For small (<= 64 bytes by default) requests, it is a caching
    allocator, that maintains pools of quickly recycled chunks.
  * In between, and for combinations of large and small requests, it does
    the best it can trying to meet both goals at once.
  * For very large requests (>= 128KB by default), it relies on system
    memory mapping facilities, if supported

The differences between memory allocated by sbrk() and mmap() are: 1). A released memory map does not create any "hole" that would need to be managed. 2). mmaped regions must be page-aligned. 3). invoking mmap and mfree is much slower than carving out an existing chunk of memory, because mmap will force kernel to zero out the memory it returns, which eats a lot of cache and memory bandwidth.

The basic memory structure in glibc malloc is:

struct malloc_chunk {

  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */

  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;

  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free.  */
  struct malloc_chunk* bk_nextsize;
}; 

There are two core elements in dlmalloc: Boundary tags and bins.

Basically, boundary tags are how memory chunks look like, and bins are how memory chunks are managed.

An allocated chunk looks like this (boundary tags):

    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of previous chunk, if allocated            | |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of chunk, in bytes                       |M|P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             User data starts here...                          .
            .                                                               .
            .             (malloc_usable_size() bytes)                      .
            .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of chunk                                     |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of previous chunk                            |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    `head:' |             Size of chunk, in bytes                         |P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Forward pointer to next chunk in list             |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Back pointer to previous chunk in list            |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Unused space (may be 0 bytes long)                .
            .                                                               .
            .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    `foot:' |             Size of chunk, in bytes                           |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Bins
    chunk in a list is known to be preceeded and followed by either
    inuse chunks or the ends of memory.

Fastbins
    A single-linked LIFO array of lists holding recently freed small chunks.
    Chunks in fastbins keep their inuse bit set. malloc_consolidate
    releases all chunks in fastbins and consolidates them with
    other free chunks.

the "unsorted" bin
    chunks being placed on it in free (and malloc_consolidate),
    and taken off (to be either used or placed in bins) in malloc.

Binmap
    a bitvector recording whether bins are definitely empty so they can
    be skipped over during during traversal

First kernel patch

My real first kernel patch. I am quite exciting about it. Finally I got a Signed-off-by in the kernel commit log :)

Luckily enough, the patch got merged just before 2.6.30-rc3 was released.

commit ac046f1d6121ccdda6db66bd88acd52418f489b2
Author: Peng Tao
Date: Mon Jul 13 09:30:17 2009 -0400

ext4: fix null handler of ioctls in no journal mode

The EXT4_IOC_GROUP_ADD and EXT4_IOC_GROUP_EXTEND ioctls should not
flush the journal in no_journal mode. Otherwise, running resize2fs on
a mounted no_journal partition triggers the following error messages:

BUG: unable to handle kernel NULL pointer dereference at 00000014
IP: [] _spin_lock+0x8/0x19
*pde = 00000000
Oops: 0002 [#1] SMP

Signed-off-by: Peng Tao
Signed-off-by: "Theodore Ts'o"

Valerie's Advice to FS Developpers

From an interview from Linux journal.
Keep it in mind...

Keep talking to other file system developers face to face, keep experimenting with new file systems, keep talking to people in research and academia, keep paying attention to hardware trends. The way to avoid the “file systems are a solved problem” echo chamber is to stay in touch with both each other and the outside world.

Content Addressable Storage -- The Next Step

Recently, I was writing an slightly modified version of implementation of Content Addressable Storage (CAS) for our on-line image servers. I found it a perfect choice to apply CAS to image servers, where images are uploaded once and never changed, and where disk access throughput is a main bottleneck to many large-scale on-line image service providers.

As explained on wikipedia, CAS is a mechanism for storing information that can be retrieved based on its content, not its storage location. It is typically used for high-speed storage and retrieval of fixed content.

CAS Characteristics:
1. Storage is identified by its content
2. Designed to make the searching for a given document content very quick
3. Works most efficiently on data that does not change often

Currently, most servers store images as common files and rely on filesystem's mechanism to optimize reading speed. However, filesystems are limited by POSIX standards and are optimized only for everyday usage. For large-scale image servers (or any application storing large amount of images), CAS will be a better choice (for the following reasons).

1. deduplication: both block-level CAS and file-level CAS achieve efficient storage utilization by storing same data only once.
2. Aggregation: log-structured extent-based on-disk object-stores, storing many images continuously in a single large file, resulting only one disk seek if index files are saved/managed in-memory (verses 2~3 disk seeks per read for common files).

My CAS implementation is written by the fact that most images are small files (~10MB) and there are huge amount of them on image servers. The implementation should speed up accessing of these image files. I am planing some benchmarks this week and hope to post them here soon.

After that, I will be writing a paper illustrating the opportunistic of applying CAS system to large-scale image servers. Then, I also want to explore the possibility of changing the interface (to, maybe dbus?) and make it runnable on common desktop, because current gnome/kde also read a lot of thumbnails. Maybe I can make it quicker somehow. Who knows :)

Easter egg in opensuse grub

Yesterday I booted my laptop while shaking it. First I saw some error messages saying something like "not enough memory". Then amazing things happened. A beautiful grub boot screen came into my eye. It's a snowy background with several penguins running around. I'm impressed! After booting into my system, I decided to find out what actually happened.

opensuse grub uses a gfxmenu option in menu.list to set the colorful boot menus. In my case,

gfxmenu (hd0,2)/message

So I need to open (hd0,2)/message to see what's inside.

$cp /boot/message ~/test/grub/
$cpio -i <>

Good, let's first see the about file

$cat pabout.txt
Penguin theme originally made by Raphael Quinet
(http://www.gamers.org/~quinet/lilo/).
Modernized for openSUSE by Steffen Winterfeldt.

Like it or hate it? Edit gfxboot.cfg in /boot/message
to have it always or to get rid of it.

So gfxboot.cfg next. I found an option setting penguin theme there.

; penguin theme likelihood (in percent, -1 = auto)
penguin=0

Wow, the likelihood is set 0, which explains why I didn't see the theme before. I must be so lucky that my shaking hands made grub to read the bit wrongly and presented the penguin theme to me. What a lucky dog I am!
I really like the penguin grub theme. So I decided to have it always by setting penguin likelihood to 100. and then reinstall the picture. Of course don't forget to delete the original message before archiving the new one.

penguin=100
$rm message
$find ./ -print | cpio -ov > message
./
./message
./16x16.fnt
./back.jpg
./en.hlp
./en.tr
./gfxboot.cfg
./init
./lang
./languages
./pabout.txt
./panim_a.jpg
./panim.jpg
./pback.jpg
./phead.jpg
./timer_a.jpg
./translations.en
835 blocks
$mv message /boot/

OK, let me reboot to see the new grub theme.

For those who want to try opensuse grub, please download from the official repository (look for grub here). To install grub in command line, see here. Of course root privilege is needed.

tesseract-ocr: jpeg support added

I just pushed some patches to the github host to add jpeg image support with libjpeg.

One drawback is that, because the image operation infrastructure in tesseract doesn't allow passing libjpeg private structures between open and read operations, I have to open the file stream twice in opening and reading jpeg images.

To test the patch, pull from git://github.com/bergwolf/tesseract-ocr-copy.git and build tesseract-ocr. Then run some tests, this time against jpeg images :)