Sunday, December 27, 2009

Comprehensive graphical Git diff viewer

Since a long time, I was looking for a graphical git diff viewer which could show original and modified file side-by-side and highlight the changes. There are few solutions but none of them is sufficient:
  • A tool included with git called 'git-difftool' is partially helpful -- it can show changes graphically but diff for each file is shown one-by-one. This is very irritating. In fact, unusable even with just 10-15 files.
  • Another alternative is the meld diff viewer which is "git aware". The problem here is that it can show diff for uncommitted changes only which is very limiting. What if you want to see what changes between Linux kernel, say 2.6.33-rc1 and 2.6.33-rc2? or changes between last two commits? meld cannot do it, AFAIK.
  • Finally, with kompare, you can do something like: 'git diff master | kompare -o -'. This method however, does not show original and new files side-by-side. It is simply prettier diff highlighting.
None of above methods are sufficient. So, I wrote the following script which solves our problem: show complete contents of original and new files and highlight the differences.

This script reconstructs (sparse) tree containing modified files. This is very useful with large projects like the Linux kernel -- there is one Kconfig file in each directory, which is the one this change modified!

To use it, just use the script instead of 'git diff' directly. Arguments to this script are the same as if you are using git-diff command. See script comments for further help.

Lets see some examples:

1) I have a 'qemu-kvm' git tree with some uncommitted changes. In this tree 'git diff', without any arguments, would generate the diff. So, we do the same with git-diffc.
git-diffc

2) I want to see difference between Linux kernel 2.6.33-rc1 and 2.6.33-rc2. This can be done with 'git diff v2.6.33-rc1 v2.6.33-rc2' which will generate unified diff between these two releases. To get graphical diff (note: we always use same args as git-diff):
git-diffc v2.6.33-rc1 v2.6.33-rc2
Here is the output with default (kdiff3) diff viewer:



Note that entire directory hierarchy is reconstructed which is almost essential for such large projects. A simple flat list of changed files will be almost useless. As another example if you were simply interested in checking what files are modified across these two versions, you could do:
DIFF_BIN=/usr/bin/tree git-diffc v2.6.33-rc1 v2.6.33-rc2

The same command as above, but overriding diff viewer (see script comments for details).
I hope you will find this script useful. Happy Hacking and Happy New Year!


You can download the script from here.

Wednesday, September 23, 2009

Linux kernel workflow with Git

You worked on some part of Linux kernel. It works great. Now, how to generate the patch series and send it out for review? For this, I always used to generate diffs, create a set of draft mails (one for each patch) in KMail or Thunderbird, and send all these mails one-by-one. This workflow quickly became a big headache. Then I learned Git (and some related tools) to do all this from command line and wow! what a relief!
This is just a quick dump of my notes which I made while struggling to make it all work. There are probably many other (most probably, better) workflows but this is what works for me. I hope you will find it useful. Any comments/suggestions welcome!

Why workflow with KMail/Thunderbird was bad?

Firstly, for any Linux kernel patch series, the convention is to create an introductory email a.k.a. PATCH [0/n] where 'n' is number of patches in series. Then, all the following patches should be sent as reply to this introductory patch (so, if someone is not interested in your patches, they can simply collapse the thread). For example:
[PATCH 0/3] my super kernel feature
        |-> [PATCH 1/3] this is part1
        |-> [PATCH 2/3] this is part2
        |-> [PATCH 3/3] this is part3
With KMail or Thunderbird, I could not find any clean way to compose draft mails with this threaded structure. If when you compose drafts with this threading, it screws-up patch ordering while sending.
Secondly, almost all graphical email clients have the habit of tinkering with the text and corrupting the patch. BTW, this is not a problem with KMail atleast (Linux kernel includes documentation on how to avoid this problem with other email clients too, including Thunderbird).

Thirdly, whenever you have to send a patch series, you have to re-create entire To: and Cc: list. This can become quite cumbersome -- as more and more people review your code, this list can become quite long.


Workflow with Git

Creating patches:

Method 1:

Suppose you have Linux kernel tree with two branches: mywork and master. You make series of changes (commits) to mywork branch. If you have a clean work history -- i.e. last 'n' git commits reflect incremental development of your work then you can simply use following to create set of patches ready for submission:
git format-patch --cover-letter -o patch_dir master
Options:
    --cover-letter: also generate 'patch' that introduces your patch series.
    -o: specifies directory where to store patches created (patch_dir here).
    master: replace this with branch to diff against
(as usual, see man page for all other options and details).

This creates patch files:
out/0000-cover-letter.patch
out/0001-great-new-feature-something.patch
out/0002-great-new-feature-something-more.patch
... and so on.

The filename is based on first line of git commit message.
Each patch file begins with subject line:
[PATCH 0/n] <first line of git commit message> 
and rest of git commit message as the body, then followed by the actual patch.
If you want to omit automatic appending of '[PATCH 0/n]' part to the subject, you can use '--keep-subject' option for git format-patch.
Now, review subject and body for each of these patches -- especially cover letter which is, of course, without proper subject or body when initially created.

Method 2:

Sometimes you don't have a clean working history i.e. last 'n' commits do not represent incremental development of your work. This is usually the case with me. In my case, all development happened outside mainline. To prepare patches against mainline, I commit all files in one-go and make lot of small commits later as cleanups, bug fixes are done.
In such case, you can create another branch which has a 'clean' history by carefully committing changes in correct order to this new branch. Then, you git format-patch (as in Method 1) to generate patch series. However, I usually do following -- no good reason to prefer this but it just better suits my laziness.
Since my git commit history is full of uninteresting small commits, I create individual patches manually. For each patch, I hand-pick set of files to create patch like this:

git diff --patch-with-stat master path/to/file1 path/to/file2 patch/to/file3 > 0001-great_new_feature_something.patch
git diff --patch-with-stat master path/to/file4 path/to/file5 > 0002-great_new_feature_something_more.patch
.... and so on.
Note that patch file names contain numbering (like '0001') so that git send-email picks patches in correct order (more on this later).
In the beginning of each of these patches, add the following lines:
Subject: [PATCH 1/n] subject for patch1 ('n' is no. of patches)
<message body describing patch>
Signed-off-by: Your Name email@domain.com
--- (three dashes)
<actual patch as generated by git diff>
Also create 'cover letter' that introduces your patch series. Give it any filename but prefix it with '0000' (for example, 0000-cover-letter.patch), to make sure git send-email picks this patch for sending before any other patch (more on this later).

Sanity check for patches:

Verify that your patches follow all Linux kernel coding style (and some other basic sanity checks) by using checkpatch.pl script included with linux kernel:
linux_source/scripts/checkpatch.pl <patch filename>

Sending patches:

Now the patches are prepared and sanity checks are done, its time to send these patches out for review. We will use git-send-email for this.
First, prepare and address book containing entries for all the recipients. I use abook which I found very easy to use. With abook create this address book and export it as 'mutt alias' file (using 'e' for export, followed by 'c' for mutt alias format). This mutt alias file will be used by git send-email.
Now add following to linux_source/.git/config:
[user]
name = Your Name
email = email@domain.com
[sendemail]
aliasesfile = /path/to/email_aliases_file
aliasfiletype = mutt
smtpserver = smtp.gmail.com
smtpserverport = 465
smtpencryption = ssl
smtpuser = email@domain.com
to = alias1
cc = alias2
cc = alias3
cc = alias4
(these smtp settings are for gmail accounts).
where, alias1 etc. is the string appearing between 'alias' and actual email address in mutt alias file created above.
Now, we are ready to send it out to world. We want to send all patches as reply to the cover letter (a.k.a patch 0), as is the convention used on LKML. Send it with:
git send-email --no-chain-reply --suppress-cc=sob --suppress-cc=self patches_dir
Options:
    --no-chain-reply: Don't send every patch as reply to previous patch. Instead, what we want is to send all patches as reply to _first_ patch (i.e. the cover letter).
    --suppress-cc=sob: Don't Cc email mentioned in 'Signed-off-by:' line in each patch.
    --suppress-cc=self: Don't send a copy of patches to you.
(If your requirements are different, then man git-send-email is always your friend!)

git send-email seems to pick patches in alphabetical order. So, 0000-cover-letter becomes the first patch. All other patches are sent as reply to this one. At last, before actually sending patches, add ‘—dry-run’ option to git send-email and make sure everything looks okay.
That’s it!

Friday, June 19, 2009

Fedora 11 on ThinkPad W500

This was the release I was waiting for! The installation was a bit of a trouble but it was surely worth the effort. Its really the first Fedora release that I really liked. Its stable, has good hardware support and boots really quickly (<20 seconds on my system).

In my case, Windows 7 RC was already installed on one partition, so Fedora 11 (x64) was installed in second partition. So, now I have dual boot configuration – the windows boot loader presents option to continue booting windows or launch GRUB from Linux partition. I didn’t want GRUB to be present in MBR as I experiment a lot with Linux system – so, its better if I have a working system even if I blow up Linux installation :)

The installation was smooth except for the disk partitioning step. Anaconda kept crashing while creating partitions. After a few attempts, I finally got this partitioning scheme:

Partition Mount point FS type Size
/dev/sda5 /boot ext3 200M
/dev/sda6 NA Linux LVM 43G

/dev/mapper/vg_vflare-lv_root

/ ext4 36G

/dev/mapper/vg_vflare-lv_swap

swap swap ~6G

/boot FS type has to be ext3. Its not allowed to be ext4.

Package selection step was smooth (as usual I selected KDE). Then comes boot loader options. I selected boot loader to be installed on first sector of boot partition (/dev/sda5 here), so I can later configure Windows boot loader to load Linux.

The system failed to boot after installation! For some mysterious reasons Linux installation overwrote MBR even though I selected Linux boot loader to be installed on boot partition. Fortunately, the recovery was easy. I rebooted with Windows 7 DVD and it presented Repair Windows –> Startup Recovery option which allowed recovering the MBR. This at least allowed Windows to boot again. Phew! But now, there was not trace of Linux. We have to now setup Windows to dual boot Linux.

Setting up Win7 and Fedora dual booting

Win7 uses something called BCD (Boot Configuration Data) to manage boot loader related stuff. With Windows XP you could simply extract first 512 bytes from Linux boot partition using ‘dd’ command, save this file in ‘C:\’ and add an entry for this boot sector file in ‘C:\boot.ini’ file. However, with BCD things are bit complex – boot.ini no longer exists. After lot of googling and experimentation I could not figure out how to add entry for Linux in Win7 boot loader.

Finally, I found a program called EasyBCD 2.0 beta (‘stable’ version of EasyBCD didn’t work). This program allows adding Linux as one of entries in Windows boot loader:

EasyBCD

While adding the entry, select Linux boot partition from ‘Devices’ list. In above case, Partition 4 is the boot partition. Remember that /boot partition is only 200MB and only ‘Partition 4’ is listed as ‘0 GB’, so we can guess that this the one we need to select. I selected the entry name as ‘NeoSmart Linux native’ but you can be smarter and call it ‘Fedora 11’ or something.

Once the entry is added, you will see it listed as one of Windows boot loader boot options. Selecting it will take you to GRUB installed on the Linux boot partition. That’s it!

Into the Linux

Fedora is now up and running natively. Everything worked out of box. Wireless network detected, suspend and hibernation worked perfectly. The KDE 4.2 looks simply awesome!

Only thing that’s a bit annoying is that tapping on touchpad is not detected as a click. Till now I haven’t found a solution for this. Also, this system has switchable graphics (ATI FireGL 5700 / Intel integrated crap). I have set integrated Intel graphics card as default in BIOS, so I don’t how well ATI plays with this version of Fedora.

Next Steps

As expected from a Linux box, MP3 and tons of video formats do not play by default. With Fedora 11, fortunately its now almost trivial to get these working.

First you need to add rpmfusion-{free, nonfree} repositories as shown here.

For MP3 support:

  • yum install audacious* # if you use Audacious audio player (my favourite!)
  • yum install xine* amarok* #if you use Amarok (this used to be my favourite)

For various Video formats:

  • yum install smplayer* # smplayer is a simple and nice video player.

This installs lots of codecs (as dependency of smplayer) to play nearly all file formats: flv, mpg, mov etc. etc.

Adobe Flash:

Since this is a 64-bit system, you need to download Flash Player 10 pre-release from here:

http://labs.adobe.com/downloads/flashplayer10.html

tar-unzip the file and copy the libflashplayer.so file to /usr/lib64/mozilla/plugins. Restart Firefox and test with some YouTube videos.

DeltaRPMs:

Install yum-presto plugin. This causes yum to download only the ‘delta’ between two version of packages resulting in much smaller download during upgrade.

  • yum install yum-presto

and now, upgrade all packages:

  • yum upgrade –y

Misc Notes:

  • By default, KDE4 Konsole does not read ~/.bash_profile on startup. To do this, change Konsole Shell command (using ‘Settings –> Edit current profile’) to:

/usr/bin/bash --login

  • With default ‘Oxygen’ style, its difficult to distinguish active and inactive windows. So, my personal preference is to use ‘Plastique’ style which looks much better and is easier on eyes.
  • To get that Lion (‘leonidas’) wallpaper :)

yum install leonidas-backgrounds*

Sunday, May 10, 2009

Windows 7 RC on ThinkPad W500

Today I replaced Vista (32-bit) on my Thinkpad W500* with shiny new Windows 7 RC (64-bit). Now just waiting for Fedora 11 to be released for dual boot with Windows – yeah, sometimes Virtual Machine is not enough!

In summary, Win7 is just awesome! Installation went smooth. Post-install some problems I faced:

- Switchable graphics didn’t work. However, ATI card works normally with switchable graphics driver (for Vista64) from Lenovo site. But since switchable graphics does not work, you have to set BIOS to use Discrete Graphics as default. I’m not much into computer gaming (occasionally NFS MW, AOE), so I have just set BIOS to Integrated Graphics considering I’m going to dual-boot with Linux once Fedora 11 is released (Linux and ATI are not good buddies).

- Fingerprint device didn’t work. Tried Fingerprint driver for Vista64 from Lenovo site but installer bails out with error “Lenovo Fingerprint Software is not supported on this version of Windows”. Didn’t try any further – its not so important :)

- Few Software incompatibility issues: MagicDisk could not mount ISO (and any other disk image) files. So, currently I have no way to mount such images. Again, not a showstopper. All “essential” stuff works perfectly – Firefox 3, Thunderbird 2, VMware Workstation 6.5.2, Sun VirtualBox 2.2.2, Vim 7.2 (failed to add “Edit with Vim” context menu entry), Visual Studio 2008, Adobe Reader 9, VideoLAN 0.9.9, Office 2007.

Keeping aside above problems, system seems much more responsive than (pre-installed) Vista crap – primarily I think due to full use of 4G RAM (pre-installed was Vista 32-bit. eh!). Startup is fast – Login screen appears within ~30 secs. Shutdown has “Force Shutdown” option – so if something is stuck during shutdown, you have option to kill that pig and proceed with shutdown. Neat.

Overall, this RC is impressive and really, this is how Vista should have been. There is nothing even remotely radical in Win7 over Vista/XP but surely good step forward in terms of performance and stability.

* Configuration: Intel Core 2 Duo (T9600, 2.8GHz), RAM: 4G, Win7 partition: 132G (~35G for Linux), Video: Switchable Graphics (Intel 45 Express + ATI FireGL V5700), Display: WUXGA (1920x1200), Wireless: Intel 5300AGN.

Thursday, March 19, 2009

ccache to speed-up Linux kernel compile

In case you are unfamiliar with ccache, its a "compiler cache". Compiling is primarily CPU intensive task. So, ccache caches compiled objects - so next time we compile same code, it reuses these objects thereby significantly speeding-up compilation.

I need to recompile Linux kernel usually several times a day, with different permutations of config settings. This almost forces a 'make clean' or 'make mrproper' which deletes all compiled objects in build tree and then we have to rebuild everything all over again. This takes enormous amount of time. ccache comes to rescue! I'm surprised why I didn't use it earlier.

To use ccache to speedup Linux kernel compile, all I had to do was 'yum install ccache' on Fedora10 system. This automatically created all needed symlinks and PATH setting. After this do make O=build bzImage; make O=build modules as usual. First time you won't notice any speed gain as ccache is simply building up its cache. Subsequently doing a rebuild 'make clean; make' will be significantly faster
To monitor ccache stats, do:

ccache -s

sample output:
cache directory /home/ngupta/.ccache
cache hit 521
cache miss 729
called for link 37
preprocessor error 1
not a C/C++ file 895
autoconf compile/link 131
no input file 766
files in cache 1458
cache size 92.7 Mbytes
max cache size 976.6 Mbytes
(Ah! how to stop blogger from messing with formatting!)

If you see cache hits not increasing while you are compiling (and this is not the first compile), this might mean that ccache currently contains useless compiled objects. In such cases, if cache size is already near max cache size, its better to clean-up ccache with:

ccache -c

and reset stats with:

ccache -z

and lastly, you can set limit on disk size used by ccache using:

ccache -M

e.g. ccache -M 1G sets max size to 1 GB – similarly you can use K, M or G suffix to specify size.

Happy compiling!


UPDATE
On Fedora-13 system, the PATH is not automatically set after 'yum install ccache'. However, symlinks from ccache to compiler names are still created. So, you just need to add /usr/lib64/ccache to your PATH manually.

Wednesday, March 18, 2009

SLOB memory allocator

Linux kernel has few SLAB allocator variants included: SLAB, SLUB and SLOB. Of these, SLOB is especially meant to be used on embedded devices -- it tries to be more memory space efficient than other SLAB variants.

Yesterday, I had a detailed look at SLOB allocator for possible use in compcache poject and found it unacceptable for the purpose. I did it in response to feedback on xvmalloc allocator -- as part of compcache patches posted of inclusion in mainline Linux kernel:
http://lkml.org/lkml/2009/3/17/116

The requirement of this project is allocation of large no. of randomly sized objects in range [32, f * PAGE_SIZE] where fraction 'f' is typically 3/4 and PAGE_SIZE 4Kb.

To begin with, SLOB maintains just 3 freelists:
- for size < 256 - free_slob_small
- [256, 1024) - free_slob_medium
- [1024, PAGE_SIZE) - free_slob_large

It allocates from one of these lists depending on size requested.

Why SLOB is bad:

1) O(n) allocation:
To find block of given size, it _linearaly_ scans corresponding free list to find a page with _total_ free space >= requested size. This free space might not be contiguous. So it runs through free blocks within each such candidate page until it finally finds some page with free contiguous area >= requested size.

2) Fragmentation: When growing SLOB cache, page is added to one of 3 freelists (depending on what size we are currently allocating). After this, this page can never move to any other list - even if its free space drops down to fall in next range below or vice versa. This has two problems:
- Potentially large wastage due to "page internal fragmentation": e.g.: alloc(3096) is satisfied from a page in 'large free list'. Now it has 1000b free (assuming 4k page) which will now never be used.
- It can trigger unnecessary cache grows: e.g.: even though we have such unfilled pages in 'large' list, allocation in 'small' range can still cause cache grow if 'small free list' is empty.

3) It only allocates from "low memory". This is clearly not acceptable for compcache on 32-bit systems.

Tag files on windows

All GMail addicts know power of tags! Surprisingly, today's systems have none/limited tag functionality for files. Fortunately I found this freeware for windows which lets you tag almost any filetype. Interface is really good with shell integration and search based on tags is fast too. A real life saver!

You can get it from:
http://www.tag2find.com/

Anti-tip of the month

Very old but still as relevant... and very interesting too! Directly go to "anti-tip" section of this article.

"The moral of the story is: don’t get tricky. C programmers often try to minimize the number of lines of C in their program without consideration for what the compiler will generate. When in doubt, write clear code and give the optimizer a chance to maximize performance. Look at the compiler output. Your code will be easier to debug and probably faster too."

Fedora 10 instability issue solved!

One of my Fedora 10 systems used to freeze very frequently. After lot of looking around I found its because of "KWin Composing" which gives OpenGL driven special effects for desktop. Unfortunately, Linux has always been bad at radeon drivers, so it better to disable these effects especially if you have radeon video cards.

in ~/.kde/share/config/kwinrc:

in [Compositing] section change
Enabled=true to Enabled=false.

Reboot after this change. Now I never get any system freeze - as is expected from solid Linux system :)

Friday, March 13, 2009

Difference Engine: Harnessing Memory Redundancy in Virtual Machines

Here is link to paper (pdf) (MP3)

Recently I came across this paper published in OSDI '08. Its an extension to VMware's page-sharing and shows some amazing and hard to believe results. VMware page-sharing mechanism scans memory for all VMs and maps pages with same contents to a single page. This achieves memory savings if multiple VMs are hosted running same OS. However, with technique discussed in this paper, we find pages that are nearly same. For such pages, they save a base page and other similar pages as delta of original page. For pages which are not similar to any other page are simply compressed. Their benchmarks shows upto 45% more memory saving over ESX page-sharing under some (specially crafted) workload.

The idea is surely very interesting but I have serious doubts if it really will be that effective for real workload. Below I give my notes on this paper and some possible extensions to this work.

Following notes refer to paper extensively. So keep the paper handy while reading these (link to paper in beginning of this post).

Notes

  • Page Sharing (for identical pages) by DE itself is much more efficient than that of ESX (with scan rate of 10,000 pages/sec). See Fig 9 and 11 in particular. After long run, ESX eventually catches up but saving is much inferior *during* benchmark.
  • For all 3 "real world" workloads (ident, MIXED-1, MIXED-2), memory saving contribution of page sharing for DE in just first few seconds is nearly 30-50%. This looks too good to be real.
  • They don't show data for any of real workloads where only *one* of mem saving mechanisms is active. We compress only the pages that are not "similar" to any other page - what are perf numbers if all pages were compressed? They only show contribution of individual methods (page sharing, delta for similar pages, compression for unique pages) but not the effect of individual methods working alone.
  • They show effect of individual methods for artificial workloads (Fig 5, 6, 7). Fig 7(b) shows big savings with patching. However this is case where pages are 95% "similar". Author has not noted in what terms they are similar. Are changes confined to end of page, beginning or at random offsets? For each of these cases patching algorithm can give significantly different patch sizes.

Comments

  • Nothing can guarantee good saving for any arbitrary workload. Authors choice of "real world" mixed workload however looks good. Proper performance evaluation with these mixed workloads should be good enough to show strength of DE however this is not done properly in this paper as noted above.
  • DE used xdelta for patching. A far more superior algorithm for this is bsdiff but this is has much higher mem/CPU requirements. Maybe work on more efficient variation is worth it.

  • Lots of performance numbers comparing different patching algorithms can be found in this thesis. (pdf)

  • Some data transforms are expected to significantly increase memory savings without much additional CPU overhead (see Future Work).

Conclusion

  • Paper does not conclusively proves that data de-duplication gives significant space savings over compression alone even for its sample "real world" apps.

Future Work

  • Collect suspend images of various VMs with mixed workloads (similar to this paper) and check effectiveness of these cases:
    • share identical pages only
    • delta encode similar pages only (with sharing of ident pages)
    • compress individual pages only
    • All combined (showing individual contributions here).
  • Compare different patching algorithms in above cases.
  • Redundancy can be artificially created: BWT# transform followed by MTF# encoding is known to generate redundancy for various kinds of data. So, I expect more effective data de-duplication with following modification to DE:

# BWT (Burrows-Wheeler transform)

# MTF (Move-to-front)

// This function is called after search
// for *identical* page fails.
EncodePage(page)
{
P1 = BWT(page)
P2 = MTF(P1)
// Typically two keys per page
keySet[] = Fingerprint(P2)
Psim = (
Find Page with at least
one key matching with keySet[]
)
if (Psim) {
// bsdiff - or some variation
// (better than xdelta used in DE)
DeltaEncode(P2, Psim)
} else {
// Expected must higher compressibility
// due to BWT+MTF already applied
CompressPage(P2)
}
}


DecodePage(encodedPage) - BWT is reversible!
BWT+MTF create more redundancy within each page and hence is expected to create more redundancy across pages. There is already a compression utility rzip that exploits this. Among other things, it applies BWT+MTF and then compresses using global dictionary. Its not useful as is but the idea can surely be used.

Thursday, March 12, 2009

RAM is not enough - Memory Compression!

This is my first post and what else I could start with!

Memory compression has been my pet project since last 2 years. It adds a compression layer to swap path -- whatever OS swaps out will be compressed and stored in memory itself. This is huge win over swapping to slow hard-disks which are typically used for swapping. Biggest challenges are what to compress? how much to compress? how to manage compressed blocks? handling incompressible data and list goes on...

This is all basically shifting load over to processor to avoid slow disks. Now in multi-core era this seems to only gain in relevance -- de/compression can be almost free if we can use all those cores smartly :)

Project home:
http://code.google.com/p/compcache/