Story of find_busiest_group() cleanup.

Last year, around the same time, I had ranted about this function named find_busiest_group() in kernel/sched.c. This is one humongous function which can so easily scare the sh*t out of any programmer who sees it for the first time. Partly due to it’s sheer size, which spanned over lines, next due to the presence of several similarly named local variables, and finally due to what appears to be a lack of organization.

Around that time, I even told dhaval that, I should stop ranting about it and get onto fixing it. But I got involved with OLS paper work and Idle load balancer tweaking. Plus there were some personal issues which kept me out of action for quite some time. All said and done, I stopped looking at that part of the code and Vaidy took over. However, I did have a chance to look at it one last time. That was when Vaidy had just started working on making the sched_mc framework from boolean to a  multi-valued variable. He asked for help understanding that code. I could have cleaned up the mess this time. But instead, the lazy bum that I am, I came up with another band-aid idea. I cooked up a “comments patch” to explain what was going on in the code, so that we could refer to it in the future. I even maintained this “comments patch” for a couple of kernel -rc releases before letting it slip over the edge of my mind.

Soon, even the community realized it’s ugliness. Just when the sched_mc boolean-to-multi-valued patch was being discussed, Peter asked for a cleanup of this function. Vaidy gave it a shot and came up with a couple of iterations. Peter had some suggestions, and he sent an RFD on those. There were a few ideas going around, but none of them got implemented. And neither did the find_busiest_group() cleanup!

So, earlier this year, when I started working on extending the sched_mc/smt framework, I had to mess around with find_busiest_group() once again. This time, I touched only a small part of that code. Nevertheless, I have to admit that, the indentations in the existing code were already making it unreadable. To add my stuff on top, would only make it worse. So, Ingo Molnar asked for clean-up of the existing code. Which meant that life came back a full circle and what I had planned to do voluntarily, came to me in as an indirect assignment!

I got only a few hours everyday to look at this, since I was busy working on some University Relations stuff around this time. All I could manage in the first few days was to move the HUGE do_while loop out of that function , into a separate helper function. But my trip to my hometown ensured that I had enough time to look at this code. Thanks to the network disconnect due to thunderstorms, I had nothing better to do than clean up this mess. After about 6 hours of refactoring, compile testing and incremental splitting, the patchset was ready for posting.

I post this at 3:00 PM yesterday afternoon just before heading to a fairly long meeting. When I come back at 4:30 PM, the code is in linux-2.6-tip tree in origin/sched/balancing branch. Usually, a change which touches an important part of the scheduler (in this case, it’s right at the heart of the load-balancer code!) takes time to go in. I had given myself about a week inorder that it can be thoroughly reviewed.

But the posting was not without errors. In my hurry to post the patches, I forgot to compile test the last patch in the incremental series and hence, there was a build failure which I failed to catch. It was a stupid typo, which was fixed. Another few hours and this code moved into tip-master branch.

And I just saw the scheduler git-pull request on the linux kernel mailing list. It contains the cleanup patches, which means that these patches will hit the mainline kernel soon.

Lessons learnt: After spotting the right problem, don’t take a year to solve it.

Okay, in case you’re wondering what’s the fuss all about, here’s how that piece of code looked before the cleanup and here’s how it looked after the cleanup.


About gautshen

A jack of many trades of which , Linux Kernel Programming puts food on the table. Also pursuing his PhD in the area Theoretical Computer Science at the Chennai Mathematical Institute. Is an avid reader interested in the Hindu traditions and philosophy. Loves Bicycling and Good Music. Name is Ranjal Gautham Shenoy.
This entry was posted in experiences, geek, linux and tagged , , , , , . Bookmark the permalink.

2 Responses to Story of find_busiest_group() cleanup.

  1. dhaval says:


  2. ego says:


    Sorry for the comments moderation. I guess you’re commenting for the first time since I moved to this new blog. It’s a first time check and allow policy that I have enabled.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s