Random Walk of Life

No, I am not talking about Eric Clapton’s song or Jeffery Archer’s senti short story.

I am refering to Number Theory, a subject which I have liked and aced since my high school upto my engineering. We had Number Theory and Cryptography as an elective and it was one of the most challenging papers I have written till date. And the most interesting one too.

But sadly for the past two years, I have been out of touch.

So, this friday when I was at Sapna book house , and I couldn’t help noticing this book.

Bought it off and am going through the book now. Brings back the sweet old memories of the well-lit room in the 8th Block hostel room, with Shuaib crumpled on the bed going through the faded xerox material, Vaiju on the floor, me on the table and Madhu on the other bed, all of us trying to solve some assignment problem on primitive roots. And the excitement when one of us found a solution or even understood a complicated theorem. And the pride in explaining how the thing works!

Ah, well! Those were the days

Ever wondered why can’t we have a chat-bot that responds when we’re idling or away ?

Sathya tried this a couple of times while he “appeared” to be away on GTalk by responding something like “The recipient of your message is currently inactive”.

One could argue saying that the status should reflect what the person is doing. But then, more often than not, my friends’ status always say they’re Busy, but ping them, and you’ll end up spending an hour or two chatting nonsense!

Anyway, requirement or not, I think it’s a pretty cool thing to have a Bot that can respond on your behalf. Even better, how about integrating a “Mirror Bot” which echoes back whatever the buddy has just typed, or a “Emacs Psychiatrist Bot” which will piss the shyte out of your buddy?

Hmmm.. Probably against the social networking etiquettes.

Thoughts on that?

It’s been some time since I last posted something. Had been busy gathering data for the OLS paper and once that was done, got some time to look into the couple of months old CPU-Hotplug issue. There are some more items to be done there, hopefully will get some free time this month.

Read this post earlier today:
http://contentconsumer.wordpress.com/2008/04/27/is-ubuntu-useable-enough-for-my-girlfriend/

How easily people can confuse monopoly with standards.

When someone says Linux is not user friendly, I ask “Compared to what?” and they say “Windows”. My question is, what if someone who has worked on Linux all his life was shown a windows box? How will he/she feel about it?

Given the fact that number of schools today, in the name of “Computer Education” bias the young and impressionable minds by teaching them the basics of Microsoft this-or-that product and tell them, “Children, Windows is an operating system. Operating system is windows”, how justified are we in blaming everything to be a problem with Linux? I agree, there are a number of issues that can be improved in Linux. Whether it is the kernel, or the applications, there’s always that scope. But accusing that “Linux is bad because it does not behave like windows” is a stupid thing to do.

To give you an example, I have a young nephew who is not that much exposed to computers. His only knowledge of a computer is restricted to “Computer has a monitor, a processing unit, a keyboard and mouse”.

The last time he came home, I was working on my home PC which has Fedora 8 on it. He wanted to see how the “Computer” works. I showed him a couple of things. Simple things such How to use the calculator with different base systems, use Firefox to browse the internet, what games are available. And yes, I showed him Compiz Fusion. He spent the rest of the time browsing through my pictures and videos. Didn’t call me for help. Not even once.

Next time I met him, he told me about this “computer with a My Computer on the desktop” that his friend had. He told me how stupid was this browser with no tabbed features on it. How everytime he wanted to do something, it asked him thousand times “Are you sure you wanna do this?” and how irritating the whole experience was.

So, that brings me back to the basic question, does it make any sense in comparing two different operating systems, when you are already have a biased opinion in favor of one of them?! How can you expect such a comparison to be objective? Is the way to make Linux operating system a more user friendly one by mimicking what windows does, or by educating people about Linux?

I guess, these are things one needs to understand before doing Experiments on the girlfriend or grandma.

PS: One of my friends wanted to connect her windows laptop to my Hathway modem. When things didn’t work, she insisted on rebooting the modem. On doing that, things started working! Hmm.. must be a Bug Feature. Because on Linux, I just need to set the static IP using my Network Manager! It doesn’t ask me to reboot the modem

While working on idle power management, I used vaidy’s klog based patches to profile an idle system to obtain stats such as:

* The time when a cpu enters into the tickless idle mode
* The various interrupts that bring the cpu out of idle state.
* The timers that expire in this interval and cause a wake up.
* The tasks that demand/ or are made to be wake up on the idle cpu.
* The time when the cpu comes out of the tickless idle mode and starts executing the tasks.

While observing the task wakeup instrumentation data, I noticed that the wakeup statistics for kondemand appeared pretty strange. For the uninitiated, kondemand is a kernel thread that belongs to the ondemand governor of cpufreq subsystem, which changes the p-states of the system, based on the utilization statistics. Thus it’s something that helps in power management.

root@llm43 tests]# ps aux | grep kondemand | head -4
root 1143 0.0 0.0 0 0 ? S< 09:21 0:00 [kondemand/0]
root 1145 0.0 0.0 0 0 ? S< 09:21 0:00 [kondemand/1]
root 1146 0.0 0.0 0 0 ? S< 09:21 0:00 [kondemand/2]
root 1147 0.0 0.0 0 0 ? S< 09:21 0:00 [kondemand/3]

From the file wakeups.txt, an output of my profiling experiment,

pid cpu nr_wakeups
————————–
1143 0 468
1145 1 279
1146 2 78
1147 3 68

Couple of things bothered me here.

1. The unusually high number of wakeups on CPU0 and CPU1. kondemand was wakeing up approximately at the rate of 4 time and 2 times respectively on these cpu’s over a observation idle period of 120 seconds.
2. The difference in the number of wakeups by kondemand on the different CPUs.

Bewildered, I fired a mail to Venki asking for possible explanations.
And I started looking at the code. Now, the number of times the kondemand thread is supposed to check for a change in the frequency is determined by this sysfs tunable called sampling_rate. It was set to 256000us on my system. Which accounted for the unusually high number of wakeups on the CPUs.

But I was still confused. The sampling_rate is a global tunable which maps to the variable dbs_tuners_ins.sampling rate, which is common to all the kondemand threads. Then why the different wakeup rates on different CPUs?

Venki replied to my original query reminding me that kondemand uses deferrable timers! That explained everything.

Deferrable timers, behave normally on a busy system. But on a idle system, when are about to decide when should we wake up next inorder to service the next timer in the list, we skip any deferrable timer we encounter.Thus, a deferrable timer on an idle cpu would expire when the next nearest *hard* timer would expire.

So, the reason why CPU0 and CPU1 were having such high number of wake ups on an idle system can be accounted to the fact the expiry of some other timer like the ehci_watchdog would trigger the expiry of kondemand timer, and along with it the wakeup of the kondemand thread! And depending on the number of timers that are queued on different CPUs, we have the corresponding number of wakeups of kondemand thread!

So, what I was thinking to be the major cause for wakeups in the kernel, turned out to be an effect of the expiring timers queued by a totally unrelated subsystem, thus confirming the old wisdom of mathematical logic: “If two events occur one after the other, it doesn’t necessarily imply that one is the cause for the other”

Q: How many Lawyers does it take to change a light bulb?

A: Whereas the party of the first part, also known as “Lawyer”, and the
party of the second part, also known as “Light Bulb”, do hereby and forthwith
agree to a transaction wherein the party of the second part shall be removed
from the current position as a result of failure to perform previously agreed
upon duties, i.e., the lighting, elucidation, and otherwise illumination of
the area ranging from the front (north) door, through the entryway, terminating
at an area just inside the primary living area, demarcated by the beginning of
the carpet, any spillover illumination being at the option of the party of the
second part and not required by the aforementioned agreement between the
parties.
The aforementioned removal transaction shall include, but not be
limited to, the following. The party of the first part shall, with or without
elevation at his option, by means of a chair, stepstool, ladder or any other
means of elevation, grasp the party of the second part and rotate the party
of the second part in a counter-clockwise direction, this point being tendered
non-negotiable. Upon reaching a point where the party of the second part
becomes fully detached from the receptacle, the party of the first part shall
have the option of disposing of the party of the second part in a manner
consistent with all relevant and applicable local, state and federal statutes.
Once separation and disposal have been achieved, the party of the first part
shall have the option of beginning installation. Aforesaid installation shall
occur in a manner consistent with the reverse of the procedures described in
step one of this self-same document, being careful to note that the rotation
should occur in a clockwise direction, this point also being non-negotiable.
The above described steps may be performed, at the option of the party of the
first part, by any or all agents authorized by him, the objective being to
produce the most possible revenue for the Partnership.

Discovered it as one of the fortune riddles

Okay, henceforth decided to give the opening and closing mood a break!

Anyway, I am currently reading the Linux scheduler load balancing code. And there’s this one function called find_busiest_group() which looks something like this:

/*
 * find_busiest_group finds and returns the busiest CPU group within the
 * domain. It calculates and returns the amount of weighted load which
 * should be moved to restore balance via the imbalance parameter.
 */
static struct sched_group *
find_busiest_group(struct sched_domain *sd, int this_cpu,
 	   unsigned long *imbalance, enum cpu_idle_type idle,
 	   int *sd_idle, cpumask_t *cpus, int *balance)
{
   struct sched_group *busiest = NULL, *this = NULL, *group = sd->groups;
   unsigned long max_load, avg_load, total_load, this_load, total_pwr;
   unsigned long max_pull;
   unsigned long busiest_load_per_task, busiest_nr_running;
   unsigned long this_load_per_task, this_nr_running;
   int load_idx, group_imb = 0;
  #if defined(CONFIG_SCHED_MC) || defined(CONFIG_SCHED_SMT)
   int power_savings_balance = 1;
   unsigned long leader_nr_running = 0, min_load_per_task = 0;
   unsigned long min_nr_running = ULONG_MAX;
   struct sched_group *group_min = NULL, *group_leader = NULL;
  #endif

	max_load = this_load = total_load = total_pwr = 0;
        busiest_load_per_task = busiest_nr_running = 0;
 this_load_per_task = this_nr_running = 0;
 if (idle == CPU_NOT_IDLE)
 	load_idx = sd->busy_idx;
 else if (idle == CPU_NEWLY_IDLE)
 	load_idx = sd->newidle_idx;
 else
 	load_idx = sd->idle_idx;

	do {
 	unsigned long load, group_capacity, max_cpu_load, min_cpu_load;
 	int local_group;
 	int i;
 	int __group_imb = 0;
 	unsigned int balance_cpu = -1, first_idle_cpu = 0;
 	unsigned long sum_nr_running, sum_weighted_load;

Now by the time I reach this point, I am kinda confused asto what variable holds what value and represents what load exactly!
I guess, I need to increase the stack size of my mind to keep track of soo many local variables!

PS: I apologise for the formatting. The [sourcecode] macro of wordpress cannot do any better than this.
Sathya is planning to write a simple script to convert C code into color coded html instead.

Opening Mood: Hungry..
Opening song: Hamesha tum ko chaaya - Devdas

Got the official mail today morning. The “Power Aware Scheduler” Birds of Feathers Session Proposal that I had submitted for this year’s Ottawa Linux Symposium has been accepted. The rest of the BOFS can be found –> here

A couple of days back, Vaidy got confirmation that the paper “Energy-aware task and interrupt management in Linux” of which I am a co-author, has been selected! So it’s great news on the work front!!

The rest of the papers for this year’s OLS can be found –> here

OT, it has been a pretty silent day in my mailbox. I was wondering if everyone decided to take a mass-vacation or something! Only later I came to know that vger.kernel.org is down.

With only a few weeks left to turn in the paper, we should start writing soon! The data is pretty much there with the many experiments that Vaidy has been running for quite some time now.

And me, I am have started using qgit to track the CFS development from it’s inception to it’s present magnificent form! The latest qgit-4 which uses qt-4 looks pretty cool! Much better than the earlier 1.5.5 version

Until next time,
Ciao!

Closing Song: Laree Chooti - Xulfi, Ek-Chaalis ki last local
Closing Mood: Really  hungry!

Opening Mood: I’m back!
Opening Song: Romantic Piano - Chopin

Spent the last week at this place called Kudremukh. It used to be one of Karnataka’s famous mines before the operations were shut down in 2005. So now it is just a nice little place with lots of greenery and very few people to bother an occasional guest. Which was me

I started from karkala on 4th Feb at 8:00 AM to Kudremukh. I had booked a room for myself at the Sahyadri Bhavan lodge for five days through some family contacts. Reached the place at around 9:30 A.M. The ride was very good, and one could spot a lot of trees and forests on the way. Once you cross the Mala outpost, the weather becomes quite pleasant owing to the trees around.

The room where I was put up was really a big one. It had three beds, a balcony, and an attic! All for an extremely cheap then of Rs 200 per day! The guest house has a small restaurant which serves breakfast, lunch and dinner. Again, at very affordable rates. I liked the food there. But then, I also stayed for four years at NITK Surathkal and survived the mess food. So I really shouldn’t be talking about how good the food at any place is . The place also has a very nice town park where I used to go in the evenings for a stroll.

The purpose of the vacation was to do stuff which I had always wanted to do, but never got the time. Starting problem you can say . Over the past couple of years, I have been accumulating quite a bit of technical stuff to read, and the list was only growing. So I wanted to take some time off and get started on some of those items.

Thus I had five days at a place with very little disturbance and an awesome climate. Really, I couldn’t ask for more. The working style was simple. Start with one work item, when you get bored, move on to the next one. There were no other rules. No hard deadlines to finish this or that by the end of 5 days. Just have fun

So, in the five days, I read through parts of Linux Memory management. Two years of programming the kernel, and I was still not aware of how Linux manages the memory across the various platforms it supports. So I had to go back to the very basics, starting from the 386 memory management model and then how Linux represents it using a 4 level model. After that, I read up on the Zoned Buddy Allocator, the Slab Allocator and a part of Process address space. I was using “Understanding the Linux Kernel, 3ed” and 2.6.24 kernel code as reference.

Other than that, RB-trees was something I read about and implemented during this time. It reminded me a lot about AVL trees, which we had studied in our data-structures classes. RB-trees was actually easier to implement (atleast the deletion part).

Also, read the first three chapters from Ulrich Drepper’s “What every programmer must know about memory”. The paper is true to it’s name. Especially the chapter on caches. The paper gives a very clear picture of the implications of having different levels of caches, how the cache size matters, through various well designed experiments. It should be read by anyone who is interested in doing any kind of system programming.

Other than these, did a whole bunch of fun stuff, like wrote a ascii visualization tool for trees. One of the problems I had with the Data structures lab assignement was that we had to show the output through an inorder, or a breadth order traversal. And that was not always very easy to visualize. But then I was one of those who did the class assignments when there was only one or two days left for the deadline. So I guess I am doing all the supplemental things now

Oh yeah, spent a whole evening reverse engineering this obfuscated C Code which prints the poem about the various gifts given by the true love on each day of Christmas. Am planning on writing a small article on that. How recursion was used in place of loops and how the ‘,’ operator was used for statements. It’s a code when you see, you’ll go “This hurts my brain!” . Check it out here.

And when I had time to spare, I read some chapters from Jon Bentley’s “Programming Pearls”. Another book which I would recommend to anyone interested in serious programming. This book sure is fun!

So, now that I am back, the first thing to do would be to catchup with a week of email. Oh well

Closing Song: Marriage of Figaro - Mozart.
Closing Mood: Anxious to catch up with last week’s happenings.

Opening Mood: Good Morning.
Opening Song: Boondein - Silk Route

The last and final Day of FOSS.in had some really interesting talks.

I missed the talk by Andrew Cowie, since we reached the venue pretty late. However, I managed to catch the next talk by Ulrich Drepper, the person whose article on Memory management I thought was brilliant. The talk was on “Contributing to Linux Runtime”. One of the interesting things that Ulrich mentioned was that he is looking for a new malloc implementation, one which is NUMA aware. This would really be a nice thing to work on, but I hope even applications understand the concept of NUMA so that they don’t move the threads around from one node to another.

After the lunch, we had Rusty’s talk on Talloc. Talloc stands for Tridge-Allocator, or Tree-Allocator is a hierarchial memory allocator which can be a really useful thing to prevents memory leaks owing to the programmer’s forgetfulness. There were about 150 people in a hall whose capacity was 120. I sneaked into the projector room to catch that talk and got into the hall only for the Q & A session ( I won one of those caramello koalas!). You can find the Talloc details here –> http://talloc.samba.org/

I chose to attend Amit Shah’s KVM talk over Thomas’s Real-time talk. I was hoping to see some meaty details about the KVM way of doing virtualization. But unfortunately most people in the audience had problems visualizing virtualization in the first place. So it ended up as a demo session. I guess, since the code is available, I will have to just go over it.

The concluding ceremony had “Rusty and a Merry Band of FOSS hackers” (Doesn’t that remind you of some rebel group in some corner of the Sherwood forest?) talking to the audience and sharing their experiences with open source. He showed us how easy it was for anyone to go ahead and contribute to open source projects, by asking one of the volunteers to come over and send a Documentation patch for lguest. You can find that here –> http://lkml.org/lkml/2007/12/8/49

I had to leave early to help prepare for Sunday’s barbecue. That however is another story for some other time

Closing Song: Village Damsel - Indian Ocean.
Closing Mood: Power Aware!

Opening Mood: Sleepy.
Opening Song: Walk of Life - Dire Straits.

I couldn’t attend the morning nor the afternoon session owing to some work at office. However, I managed to catch the OpenMoko talk by Harald Welte. It’s a pretty neat stuff and has got an emulator which is based on qemu which does complete hardware emulation. So you can pretty much try out the whole moko-stack on the emulator without having the handset with you. One interesting thing I realized was that OpenMoko doesn’t use cpufreq support yet. I thought that ARM did have some kind of cpu-frequency scaling support. Something reminds me of powerops. But anyway, I am planning to look into it once I get some freetime.

Next, I met with the Mozilla developer Chris Hoffman to discuss a power management related issue on Linux, when we’re running on battery. I was fooling around with powertop the other day and observed that the one application which was consistently responsible for so many wakeups in the userspace was firefox. And that too when the firefox is minimized or is in a completely different workspace than the one which is active. It did seem stupid to do that, when the whole world is worried about the rising energy costs!!! More details on that bug can be found –> here

I also met Amit Shah one of the employees of Qumranet working on KVM. Looking forward to his talk tomorrow.

And at the end of the day a whole bunch of people that included Rusty, Thomas, Harald, Rasmus Lerdorf, Amit Shah, Srivatsan, Ravi my colleagues from office and folks from ABB went out to dinner at Bombay Post. A fitting end to the day I suppose.

Closing Song: Once upon a time in the west - Dire Straits.
Closing Mood: Really sleepy. Good night!