Blogging Computer science

compiling the linux kernel easy way in ubuntu.

2010-04-19T20:55:00.000-07:00

If you are a person who likes to play with newest kernels and change the code every now and then, you might find the debian style kernel compiling too frustrating. For me it takes ages to create a dpkg kernel package. Since i configure kernel with debugginng information, its huge. even the dpkg file is few hundred MB and takes an aweful lot of time to create it using make-kpkg.

We can easily compile the kernel the old way. just do
make oldconfig/menuconfig/xconfig/whateverconfig
make
sudo make modules_install
sudo install
sudo mkinitramfs -o /boot/initrd.img-yourversion yourversion
sudo update-grub

its that easy and fast :-)

How Intel Virtualization and KVM Works?

2010-04-13T14:31:00.000-07:00

How Intel Virtualization and KVM Works?

Virtualization is a Processor technology which enables a Virtual machine to run Natively in processor (Not all Instructions) without Emulation. Your Hardware must support Intel Vt-x or SVM to support hardware virtualization.

It supports Virtualization with the use of new operating Modes called VMX root operation and VMX non Root Operation. Before Virtual machines can make use of Virtualization features, it should be turned on with VMXON Instruction. It can be turned off using VMXOFF. It is usually done by Virtualization driver when loaded. The processor runs the instruction of the virtual machine in VMX non root operation. Only certain instructions can be run in this mode. When the VM runs critical instructions like I/O (can be controlled using I/O bitmap), write to CR etc, the mode is switched to VMX root operation and the control is passed to Virtualization driver (aka VM Monitor or Hypervisor). The Hypervisor takes care of that instruction by emulating it and again enters VMX non root operation.

In KVM, the kvm driver on insert checks if the hardware supports VT-X, creates IOCTL handlers for the KVM device file /dev/kvm.

the IOCTL handles a number of operations including, getting version, getting/setting registers, creating memory map for guest, creating/destroying virtual machine instance etc.

The Application like QEMU uses KVM by doing IOCTL calls to kvm through /dev/kvm. Basically it does it through the use of libkvm. it,

calls kvm_init to inititialize kvm vmm

* it registers a set of call backs which is on when running preveledged instructions like I/O instructions.

* opens /dev/kvm and checks the versions and stuffs.

* initializes kvm_context structure and returns.

calls kvm_create to create a VM.

* it pass the size of memory vm should allocate and returns the start address (the image is loaded there.).

* creates VCPU by calling KVM_CREATE_VCPU IOCTL

* mmaps the said memory is to applications address space using mmap.

Initializes all the hardwares to be emulated.

Calls kvm_run to run the virtual machine.

* It calls KVM_RUN IOCTL to start running the VM.

These are the basic things done by the application that uses KVM but not all. I am also currently writing the brief Walk through of the KVM code which i learned while reading the KVm code.

Regards,

Manish Regmi

How to create statically linked executables in QT4?

2010-04-12T16:05:00.000-07:00

Recently i used QT for Ext2read project. (http://ext2read.sf.net).
I found out that the default installation of QT is configured such that it dynamically links with all the QT library (like QT4core.dll etc) and Mingw runtime (like mingwm10.dll). It means that you cannot just deploy the executable you created. You will need to deploy the dlls that your application use which include a lot of qt*.dll and mingw*.dll.

If you want to configure QT to generate static code, you need to compile QT statically. But that is not enough. you also need to change qmake.conf.

First go to mkspecs\win32-g++\qmake.conf and add -static in the line QMAKE_LFLAGS
now it will look like this,
QMAKE_LFLAGS = -static -enable-stdcall-fixup -Wl, ...

Now recompile your QT Library. To do that follow the steps below.
First make sure the QT bin directory and Mingw Bin directory is in your PATH envirnoment variable.
If not add C:\qt\2010.02.1\qt\bin and C:\qt\2010.02.1\mingw\bin (or wherever QT is installed) to your PATH envirnoment variable. for that right click on your computer, click properties, go to advanced system settings, click Envirnoment variables.
Now, open command enterpreter and go to qt\src directory and type
configure -static -debug-and-release -no-exceptions (NOTE: you can add any other parameters. see configure -help for details. But -no-exceptions is required.)

After the configure is run sucessfully. type,
mingw32-make sub-src

This will take a long time to compile. after it is completed you are ready to build your project statically.
To build your project as static release, type
qmake -config release
mingw32-make

You can use a tool called dependency walker to find out the dlls your application depends on. You can download it from http://www.dependencywalker.com/

Regards,
Mainsh Regmi

How Ext4 Extents Work?

2010-03-31T15:27:00.000-07:00

How Ext4 Extents Work?

Earlier Ext2 and Ext3 had the limitation on the size of the file. It used 32 bit block number to access the data blocks. So that limited the maximum size of file to be 2^32 * blocksize(eg. 4k**) = 16TB*. Also the access time for large Files were slow because in had to go through lots of indirection.Ext4 Filesystem can support very large files it has 48 bits to adress a block. Also its uses extents to store data so access time is faster for large files.

The information for the data blocks are stored in the i_data of the inode structure. In a system without Extents, the first 12 entries contains the block numbers of the first 12 blocks of data. Then
it contains the block number for the Indirect blocks. That block contains the array of block numbers which point to the data. Similarly, there is Double indirect block and triple indirect block. So if we need to get the data from a very large file, we need to go through those indirection.

How to determine if the Filesystem uses Extents or indirect Mapping?

To determine whether the inode has extent based mapping or indirect mapping. We need to look at the EXT2_EXTENTS_FL bit in the i_flags in inode structure. The root directory always has the indirect mapping instead of the block mapping.

What does the Ext4 Extents Data Structure Look like and where it is stored?

In extenxt based block mapping, the i_data of inode contains Extent structures. There is a extent header, Extent and Extent index. The following structures define those structures.

/*
* This is the extent on-disk structure.
* It's used at the bottom of the tree.
*/
struct ext4_extent {
   uint32_t ee_block; /* first logical block extent covers */
   uint16_t ee_len; /* number of blocks covered by extent */
   uint16_t ee_start_hi; /* high 16 bits of physical block */
   uint32_t ee_start_lo; /* low 32 bits of physical block */
};

/*
* This is index on-disk structure.
* It's used at all the levels except the bottom.
*/
typedef struct ext4_extent_idx {
   uint32_t ei_block; /* index covers logical blocks from 'block' */
   uint32_t ei_leaf_lo; /* pointer to the physical block of the next *
   * level. leaf or next index could be there */
   uint16_t ei_leaf_hi; /* high 16 bits of physical block */
   uint16_t ei_unused;
};

/*
* Each block (leaves and indexes), even inode-stored has header.
*/
typedef struct ext4_extent_header {
   uint16_t eh_magic; /* probably will support different formats */
   uint16_t eh_entries; /* number of valid entries */
   uint16_t eh_max; /* capacity of store in entries */
   uint16_t eh_depth; /* has tree real underlying blocks? */
   uint32_t eh_generation; /* generation of the tree */
};

(NOTE: They are stored as little endean and Linux code has __le32 types used)

The Extent is implemented as a B+ Tree. Only the leaf nodes has the Extent Structure. Others have Extent Index Structure. The extent information starts with the header and then either Extent or Extent Index.In the i_data there is only space for header and 3 more Extent structures. If more extent information needs to be stored, than whole bocks with extent index structures are used. In the non leaf nodes, extent index structures are used. It contains the block number of the block where next level of nodes are stored.
The logic can be described by the following 2 figures.

(Please click the images to see full image)

The eh_magic field in the header is always 0xf30a (little endean).
The eh_entries field determines the no of valid extents in that extent array.
The eh_depth is the depth of the B+ tree. if the depth is 0, the extents in that array are always extent structures and not the extent index structures.

I have implemented this feature in ext2read project (http://ext2read.sf.net).It hasn't been tested yet though for very large files. The Ext4 also uses HTree for directory entries. I am currently studying it and implementing.

Please let me know if you have any questions.
Manish Regmi (regmi dot manish at gmail dot com)

Installing ubuntu 9.10 on a Lenovo ideapad Y550 (or any other system that uses Intel 4500 chip)

2010-02-11T18:53:00.000-08:00

Installing ubuntu 9.10 on a Lenovo ideapad Y550 (or any other system that uses Intel 4500 chip)

I wanted to install ubuntu in my new Lenovo ideapad Y550 but the problem was i just got blank screen. Just after the CD boots and when I press to eithr install or boot through CD, I got blank screen. I could figure that the system was booting. It was just the screen which was blank.

No matter what other options I use, I could not get it to work. I tried safe mode graphics , acpi=off option and what not but all in vein. After a little study I figured out that I needed to pass, i915.modeset=0 as a kernel parameter. To do that, just press F6, esc and add that line in the end of the kernel parameter.

This has something to do with a new kernel feature called kernel mode setting (KMS). KMS is a feature now in Linux kernel which will do the work of setting your screen resolution, depth, colors, etc. Earlier this was done by the XOrg graphics drivers. For example, before the kernel version 2.6.28, when you use to change your screen resolution from your GNOME/KDE, the XOrg driver use to do it. Now the same task is moved into the Linux kernel to speed up the things. Ubuntu comes with a kernel confured with KMS and the value for 915 based chipsets set to i915.modeset=1.

There is another problem. The new ubuntu comes with a new version of grub. This not as straightforward as older one in which you just edit a file called grub.conf or menu.lst. This one is a pain in the ass to customize. If u edit the grub.cfg file to add the i915.modeset=0 parameter, the setting will be gone next time you upgrade kernel. And a new grub.cfg is generated automatically and you have to add the parameter again. Also learn to console based editors like vim, GUI editors wont let you write to the grub.cfg file.

I will write about grub customization when I have time. Enjoy ubuntu in your laptop.

Start testing power management in OLPC

2007-04-08T21:47:00.000-07:00

Start hacking OLPC for power management.

Now there are words of succsssful suspend and resume on OLPC, it is time to do some testing.
For this we need at least a B2 OLPC machine. Apart form that we need the powermgmt branch of olpc-2.6 git tree found at git://dev.laptop.org/olpc-2.6 and an experimental firmware version q2c00.rom and higher.

first download the things (git tree and firmware) in your PC
here are the steps you need to follow for flashing new firmware

put the firmware in your usb drive.
then boot the OLPC B2 machine.
interrupt the boot process by pressing "any key". (dont search wor a key named any, just press your favourate key ;))
at the ok prompt, type "flash disk:\"
eg. ok flash disk:\q2c01.rom
after updating your firmware, the system will shut down.
Now you have a power management capable firmware.

You will also need the powermgmt branch of the official OLPC kernel tree.
If you dont already have the tree just clone it.
$ git clone git://dev.laptop.org/olpc-2.6 olpc-2.6

else if you already have the tree just pull latest ones by doing
$ git pull

else if you already have the tree but not the powermgmt branch, you can pull that branch just by doing
$ git pull git://dev.laptop.org/olpc-2.6 olpc-2.6 powermgmt
But i suggest you just write this to your .git/remotes/origin file
URL: git://dev.laptop.org/olpc-2.6
Pull: refs/heads/master:refs/heads/origin
Pull: refs/heads/libertas:refs/heads/libertas
Pull: refs/heads/linus:refs/heads/linus
Pull: refs/heads/mtd:refs/heads/mtd
Pull: refs/heads/geode:refs/heads/geode
Pull: refs/heads/powermgmt:refs/heads/powermgmt
Pull: refs/heads/stable:refs/heads/stable
Pull: refs/heads/devtree:refs/heads/devtree
Pull: refs/heads/zones_of_death:refs/heads/zones_of_death
Pull: refs/heads/experimental:refs/heads/experimental

after doing git pull, all branches will be updated/created.

now switch to the powermgmt branch by doing
git checkout powermgmt

Now start editing and compiling the kernel.
make xconfig
make
make modules_install

not after everything is compiled, put the arch/i386/boot/bzImage and /lib/modules/ to your usb drive.
(Note: you can ask make modules_install to install the modules directly to your usb disk by using INSTALL_MOD_PATH variable)

now boot the OLPC and copy bzImage to /boot/ (you can rename it to vmlinuz-version to follow naming convention.) and copy modules to /lib/modules/ folder.
now reboot and start booting your new kernel.

(Note: i have troubles creating new fth file and doing setenv boot-device nand:\boot\my.fth. ??? )

Writing a power aware driver in Linux.

2007-02-20T01:32:00.000-08:00

Writing the power aware device driver is one of the most challenging task in Device driver development.
I feel that power aware device drivers are not only necessary important to Laptops and embedded devices but also to desktops. For example, my desktop with 450 Watts of power supply eats a of electricity.
Most hardwares support different kinds of power modes where they use different amounts of power. They can also be suspended and resumed But it requires that the device driver has a suspend() and resume() routine in it.
The suspend() routine is called on direct user request (eg. laptop lid close, press suspend), system power policy (eg. sleep after 30 minutes of console inactivity) or device power policy (eg. power down device after 5 minutes of inactivity). Similarly the resume routine is called when the user starts using the device again (usually known by interrupt arrival). Similarly, the resume() routine is called when an interrupt is received.

On the suspend event, the system is supposed to turn off the device or put the device in low power mode (if it supports it). But when the device is turned off , the state of the device might be lost and so can the values in its internal registers. So, the driver is supposed to store the state of the device, the value of the registers etc (actually it is device dependent). Now when the suspend function is called, the device driver, stores the Device State, value of internal registers (or whatever that is lost on power off) and it disables the device (powers it off) or changes it to low power state.

On the resume event, the system is supposed to turn on the device or put the device in “normal” mode. The important thing the driver needs to do is to restore the previous state of the device. So, when the resume routine is called the driver restores the device state. Some device may also require to run the initialization sequence of the device.

The core suspend() and resume() are actually provided by the bus drivers. They reside in struct bus_type. The suspend and resume requests are first serviced by bus drivers and they forward the request to each of the devices attached to the bus serially. Its the job of the bus driver to act on bus specific power management registers, don't touch them.

for example, if your device is a PCI device,

int mydevice_suspend(struct pci_device *pdev, pm_message_t state)
{
if (state.event == PM_EVENT_SUSPEND) {
// Save device context
// put your device into low power state
}
}

int mydevice_resume(struct pci_device *pdev)
{
// put device into normal state
// restore device context
}

static struct pci_driver mydevice = {
.name = "mydevice",
.id_table = mydevice_id_table,
.probe = mydevice_probe,
.remove = mydevice_remove,
.suspend = mydevice_suspend,
.resume = mydevice_resume
};

for more details see Documentation/pm.txt and Documentation/power/*

Blogging Computer Science.

2007-02-10T06:04:00.000-08:00

I read a lot of technical blogs. It encouraged me to write my own technical blog.
I will be writing about my experience, the trouble i come upon, problems i solved etc etc ;)