Thursday, January 20, 2011

Android: automated per-uid task group

Android is a privilege-separated operating system, in which each application runs with a distinct system identity: the Linux user ID (uid).

With this patch (sched-automated-per-uid-task-groups.patch) the kernel automatically creates a distinct task group for each uid (when a process calls set_user()) and places all the tasks that belong to a single uid into the same task group. In this way each application can get a fair amount of the CPU bandwidth (guaranteed by the CFS scheduler), independently by the number of task/threads spawned.

The patch is against the CyanogenMod's 6.1.1 kernel ( and I tested it successfully on my HTC Desire (Bravo).

I've used the following testcase:
  - run 4 cpu hogs in background as user app_35 ( in my case):

 # su - app_35
 $ for i in `seq 4`; do yes >/dev/null & done

  - run the Quadrant benchmark in parallel and measure the result with and without the patch applied

Without the patch (output of top):
 6533   123 10070    R     202m 48.6   0 20.0
 6506     1 10035    R     1128  0.2   0 20.0 yes
 6507     1 10035    R     1128  0.2   0 20.0 yes
 6508     1 10035    R     1128  0.2   0 20.0 yes
 6509     1 10035    R     1128  0.2   0 20.0 yes

Benchmark result: 676

  uid 10035 (cpu hog)  : 60.0 % cpu quota
 uid 10070 (benchmark): 20.0 % cpu quota

With automated per-uid task group (output of top):
 6784   123 10070    S     209m 51.4   0 50.0
 6852     1 10035    R     1128  0.2   0 12.5 yes
 6853     1 10035    R     1128  0.2   0 12.5 yes
 6854     1 10035    R     1128  0.2   0 12.5 yes
 6855     1 10035    R     1128  0.2   0 12.5 yes

Benchmark result: 816

 uid 10035 (cpu hog)  : 50.0 % cpu quota
 uid 10070 (benchmark): 50.0 % cpu quota

Total speedup: ~1.2 (the benchmark is about 20% faster in this case), because in the last case the benchmark gets ~50% of the CPU time and in the other case it gets only ~20%, despite the fact that there are 2 "pair" applications that should be correctly considered as equal from the user's perspective.

This patch is based on the patch "sched: automated per tty task groups" by Mike Galbraith.

Monday, January 10, 2011

HOWTO: install a custom kernel on HTC Desire

=== Disclaimer ===

I take no responsibility for anything that may go wrong by you following these instructions. Proceed at your own risk!

I tested this howto with a Bravo HTC Desire, rooted with Unrevoked 3.22.

=== Requirements ===

- A rooted HTC Desire (Bravo)

- The android SDK + NDK (to get the cross-compile toolchain):

- The latest HTC Desire kernel (choose "HTC Desire - Froyo MR - 2.6.32 kernel source code")

- The koush's AnyKernel template (to generate the at the end of the build process)

=== HOWTO ===

- Prepare the cross-compiler environment (replace /opt/android with the path where you have installed the Andorid NDK):

$ export PATH=/opt/android/android-ndk-r5/toolchains/arm-eabi-4.4.0/prebuilt/linux-x86/bin:$PATH

At this point arm-eabi-gcc, as well as other binutils and compiler binaries, should be in your $PATH.

- Untar the kernel

- save the kernel config (if you want to restore the original kernel config):
$ adb pull /proc/config.gz

- [optional] Apply the following patches to the kernel:
   - 0001-sync-disable-fsync-fdatasync-sync_file_range-syscall
   - 0002-writeback-change-default-dirty-memory-settings
   - 0003-sched-replace-CFS-with-the-BFS-scheduler

- [optional] Take my kernel configuration:
$ wget -O bravo-2.6.32-gd96f2c0/.config

Or use the previously saved config.gz either.

- Build the kernel:
$ cd bravo-2.6.32-gd96f2c0/
$ make ARCH=arm CROSS_COMPILE=arm-eabi- oldconfig
$ make ARCH=arm CROSS_COMPILE=arm-eabi-

Now you should find the fresh new kernel, ready to be flashed on your HTC Desire, in arch/arm/boot/zImage.

- Apply the following patch to the koush's AnyKernel source (to fix a syntax error when trying to flash from ClockworkMod):
   - 0001-updater-script-specify-the-mount-options-for-the-sys

- Replace the zImage in the AnyKernel template with your zImage:
$ cp bravo-2.6.32-gd96f2c0/arch/arm/boot/zImage AnyKernel/kernel/zImage

- Go back to the template directory (you will see three subdirectories: META-INF, kernel & system) and generate the
$ zip -r ../ *

- Connect your phone via a USB cable (be sure to turn on USB debugging on your phone: Settings -> Applications -> Development -> USB debugging)

- Push and the wireless module to the SD card of your phone:
$ adb push /sdcard/
$ adb push bravo-2.6.32-gd96f2c0/drivers/net/wireless/bcm4329_204/bcm4329.ko /sdcard/bcm4329.ko

- Reboot your phone in ClockworkMod recovery (power-on while holding Volume down key and select RECOVERY)

- In ClockworkMod select "apply" (confirm: choose Yes)

- Reboot your phone via "reboot system now"

At this point your custom new kernel should boot.

=== Fix the bcm4329 wireless module loading without S-OFF ===

The bcm4329.ko module can't be properly overwritten in the /system partition without S-OFF the device and so give access in read-write to the /system partition. However, we can enforce the usage of our new module binding any other writable directory to /system/lib/modules (i.e., /data/local).

- the latest ARM toolchain downloadable from the CodeSourcery site

Download and install the ARM toolchain and be sure that arm-none-linux-gnueabi-gcc is in your $PATH.

- get the latest version of busybox from git (or download a recent stable version if you prefer):
$ git clone git://

- use my busybox config file:
$ cd busybox
$ wget -O .config

- cross-compile busybox:
$ make ARCH=arm CROSS_COMPILE=arm-none-linux-gnueabi- oldconfig
$ make ARCH=arm CROSS_COMPILE=arm-none-linux-gnueabi-

- copy the busybox binary into the /data/local directory on your phone:
$ adb push busybox /data/local/busybox

- bind the directory /system/lib/modules with /data/local:
$ adb shell
$ su
# cat /sdcard/bcm4329.ko > /data/local/bcm4329.ko
# /data/local/busybox mount --bind /data/local /system/lib/modules

After this trick go on your phone check Settings -> Wireless & networks -> Wi-Fi. The wireless connection should start normally.

=== Results ===

Here is my score with this kernel using the Quadrant benchmark: 1370!