Pages

Wednesday, November 24, 2010

Polymorphic Data Structures Using C macros

Have you seen kernel source files, especially header files or any device driver implementation? They all make a heavy use of C macros. I always wondered why would anyone use C macros so much. Macros are not debug-friendly; you cannot set a breakpoint inside a multiline macros. I used to be afraid of macros until i realized during my kernel project that how benign macros could be.
For the record, C macros can be used for
  • defining "constants"
  • true inline functions with no type safety
  • enhancing readability of source code
  • writing platform independent code with help of conditional compilation
But there is more to it that can take advantage of the fact that C preprocessor runs before the compiler.
One of the more frustrating aspects of non-Object-Oriented languages like C is the apparent lack of re-usable code. For example, a primitive data manipulation structure (like a tree, queue, or list) that has been implemented in one structure cannot manipulate another structure without some workarounds. There are mainly two frequently used workarounds -
  • Copy &Paste - This means we copy the algorithm for one structure and by changing name create another data manipulation structure. Though it sounds time efficient method, maintaining different copies of same algorithm is pain and moreover if there exists any bug in algorithm, it's propagated to all copies.
  • Generalized data structures - These structures which accept only void * for data are frequently used but they come with a price too. The use of void * weakens the limited type safety of C language and allows for bugs to creep into the code. It also suffers from ppor performance because the system has to do twice as many memory references for both data and structural links.
None of the above solutions are as promising  as true object-oriented programming. But there is a way to achieve both efficiency and time safety by using making use of macros! By leveraging C preprocessor's text manipulation one can construct the C equivalent of a polymorphic data structure. Using this technique we can construct a reliable toolbox of primitive data structures that can be used in any C program, since they take advantage of C syntax and not the specifics of any particular implementation.

C preprocessor only does text substitution and does not care of the meaning of the strings. Let's take an example.
#define QUEUE(Q_TYPE, DATA_TYPE) \
struct Q_TYPE{ \
struct Q_TYPE *left; \
struct Q_TYPE*right; \
DATA_TYPE data; \
}
QUEUE(queue_t, int)  myQueue;
The above code generates a unique structure where only allowed data type is int. Hence, we get full advantage of C type safety and we can create structures for different data types on the fly. Sounds familiar? C++ templates? Then, we are on the same page.

The main power comes from the ability to generate algorithmic code which can work on these polymorphic data structure again using macros. Let's see some code -
I define a macro Q_NEW_HEAD(Q_HEAD_TYPE, Q_ELEM_TYPE) which generates a new structure of type Q_HEAD_TYPE representing the head of a queue of elements of type Q_ELEM_TYPE.

#define Q_NEW_HEAD(Q_HEAD_TYPE, Q_ELEM_TYPE) \
 typedef struct { \
  Q_ELEM_TYPE *front; \
  Q_ELEM_TYPE *tail; \
  int size;  \
 }Q_HEAD_TYPE
But I need a flexibility in choosing the link name for my structure. Hence, I define one more macro

#define Q_NEW_LINK(Q_ELEM_TYPE) struct Q_ELEM_TYPE*

This is how I can use these macros in my C program -

Q_NEW_HEAD(int_list_head_t, int_list_t);

typedef struct int_list_t{
  Q_NEW_LINK(int_list_t) myLink;
  int data;
} int_list_t;

Iterating over a linked list is the most common code, here is a syntactic sugar in the form of macros -

#define Q_FOREACH(CURRENT_ELEM,Q_HEAD,LINK_NAME)   \
 for (CURRENT_ELEM = (Q_HEAD)->front; CURRENT_ELEM; CURRENT_ELEM = CURRENT_ELEM->LINK_NAME)

Similarly we can define macros for
#define Q_INSERT_TAIL(Q_HEAD, Q_ELEM, LINK_NAME)
#define Q_INSERT_FRONT(Q_HEAD, Q_ELEM, LINK_NAME)
#define Q_INSERT_AFTER(Q_HEAD,Q_ELEM_TYPE,Q_INQ,Q_TOINSERT,LINK_NAME)
#define Q_REMOVE(Q_HEAD,Q_ELEM,LINK_NAME)
and so on ...
The program becomes much more readable and manageable. 

But, make sure to test all macro definitions for all corner cases, It's tricky to write and debug such long complicated macros. Here are some common pitfalls - well documented. Looking at the generated code may help sometimes - 

$ gcc -E my_macro_loaded_source.c


Saturday, October 16, 2010

Silicon Valley Code Camp 2010

Last weekend, I enjoyed lots of technical discussions on various new technologies including Android, Google APIs, HTML 5, Sencha Touch from some of the smartest people in the industry, together with free food and drinks and lots of swags from sponsors. Yes, this was Silicon valley code camp 2010.
It was a two day event, with 9 different tracks and over 190 sessions. The best part was it was totally FREE :) No, the best part was the learning, sharing, discussing, contemplating, questioning ... Did I mention free food? It was a huge success with close to 2000 attendees. It's a big deal because it's entirely run by volunteers.

Today I want to spend a moment to thank all those people who made this code camp a great experience for me. Special thanks to Peter Kellner for the endless hours he put in to make this possible.

I started my Day 1 with Introducing Google APIs Part-I (A-Z & Geo) session. It was quite informative given the vast variety of Google APIs. I found FusionTables very interesting and its integration with Google Maps APIs along with KMLLayer can result in some useful applications.
Then I head over to 'Android: Beyond Basics' session. Well, I was expecting to hear about some advanced topics, he covered the basic building blocks of Android except Activitiy which he had discussed in his first session, Android Basics. After lunch, I was in dilemma whether to attend Dancing with iOS or Sencha Touch. I am glad I chose Sencha Touch. David Kaneda described the Sencha Touch application framework that enables mobile web apps that look and feel native on iPhone and Android touch devices using primarily HTML5, CSS3 & JavaScript. It was like a roller coaster trip through Sencha framework. He touched so many things, it was hard to digest for a beginner like me. But I will mention few things here. David explained Syntactically Awesome Stylesheets (SASS) and the Compass framework and they together lead to more fun with style sheets. He also recommended, use of PhoneGap to prepare the Sencha Touch apps for both Android and iPhone.

Then I attended two more sessions from Google track - Google App Engine and Google Chrome / HTML 5. Both talks were equally engaging. I personally enjoyed Chrome session partly because I am currently working on Chrome OS and I could totally relate to what they were discussing. I was looking forward to day 2 for more talks on HTML 5.

I wanted to attend Do you Mapreduce? but it was clashing with 'Fun with HTML5, CSS3 and JavaScript'. This was really fun. Tab Alkins Jr (Google) coded a game live in front of audience. He covered only Canvas element so my thrust for HTML 5 was not yet satisfied and I went on to yet another HTML5 session - Mobile HTML 5 by Michael Galpin. I have read his articles on developerWorks so it was a nice opportunity to listen to his talk where he gave an detailed overview of HTML5 features. During lunch, there was a raffle with many exciting prizes including xbox which was fun (for those who won).

The session on Building Video Applications with YouTube API by Jarek Wilkiewicz was interesting because I never knew anything about it before. Some amazing statistics: YouTube gets
* 2B views/day
* 150m mobile views/day
* 24 hours of video uploaded/minute

The last session I attended was 'Mapping On The Phone' by Mano Marks from Google. It was an hands on session where he showed how to use GeoLocation feature of HTML5 together with Google Maps APIs.

It was a time for clean-up and I happily volunteered for this activity together with 10 other people. I was a nice feeling. I totally love my SVCC volunteer t-shirt :) My favorite moment was talking with Michael Galpin on video tag acceleration and application catch.

One of the side effects of attending this event is that I ended up opening my twitter account because almost everyone promised to tweet their ppt links!

Sunday, October 3, 2010

OpenGL For Android - GLSurfaceView

One of the fascinating features of Android platform is its support for OpenGL. OpenGL is a cross-platform 2D and 3D rendering graphics library. An industry consortium, called Khronos Group maintains the OpenGL specification. http://www.khronos.org/opengl/

OpenGL uses C-based flat APIs and hence we need to have a Java language binding to be able to use it with Android Application framework. Java ME has already defined this binding with JSR 231. (Java binding for OpenGL 1.5). What that means for you is - 
import javax.microedition.khronos.opengles.GL10;


Let's get started with the code. 
The main class we use is GLSurfaceView which extends from SurfaceView class. GLSurfaceView
  • Provides a Surface onto which we can render OpenGL scenes
  • Binds with customized Renderer which performs the actual drawing
  • Manages EGL display 
  • Uses a dedicated GUI thread, decouples the main application thread for user interactions
We need to call one method on its object i.e setRenderer() which registers a user specified Renderer object that knows how to draw the desired shapes. 
Activity's onCreate() will look like this - 
@Override
    public void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        this.requestWindowFeature(Window.FEATURE_NO_TITLE); 
        getWindow().setFlags(WindowManager.LayoutParams.FLAG_FULLSCREEN,
            WindowManager.LayoutParams.FLAG_FULLSCREEN);
   GLSurfaceView view = new GLSurfaceView(this);
     view.setRenderer(new SimpleRenderer());
     setContentView(view);
    }
The next thing we need is SimpleRenderer which will be responsible for actual OpenGL rendering. It implements GLSurfaceView.Renderer interface and defines its three methods.



public abstract void onSurfaceCreated (GL10 gl, EGLConfig config)

This method is called at the very beginning e.g when a Surface is created or recreated ( when phone awakes after sleep), it's a good place for all initialization code. 

A typical initialization sequence - 
@Override
 public void onSurfaceCreated(GL10 gl, EGLConfig config) {
  // Set the background color to black (RGBA).
  gl.glClearColor(0.0f, 0.0f, 0.0f, 0.5f);
                // enable smooth shading
  gl.glShadeModel(GL10.GL_SMOOTH);
         // set up depth buffer and enable depth testing
  gl.glClearDepthf(1.0f);
  gl.glEnable(GL10.GL_DEPTH_TEST);
  gl.glDepthFunc(GL10.GL_LEQUAL);
  // use nice perspective calculations.
  gl.glHint(GL10.GL_PERSPECTIVE_CORRECTION_HINT, GL10.GL_NICEST);
  
 }


public abstract void onSurfaceChanged (GL10 gl, int width, int height)

This method is called when the Surface size changes. The size (width, height) affects the aspect ratio so this function should contain the code that depends upon aspect ratio such as GLU.gluPerspective() . A sample code - 
@Override
 public void onSurfaceChanged(GL10 gl, int width, int height) {  
  gl.glViewport(0, 0, width, height);
  gl.glMatrixMode(GL10.GL_PROJECTION);
  gl.glLoadIdentity();
  GLU.gluPerspective(gl, 45.0f, (float) width / (float) height, 0.1f,
    100.0f);
  gl.glMatrixMode(GL10.GL_MODELVIEW);
  gl.glLoadIdentity();
  
 }





public abstract void onDrawFrame (GL10 gl)

This method is called when the current frame is being drawn on the Surface and thus actual drawing code goes here. e.g 


@Override
 public void onDrawFrame(GL10 gl) {
  // Clears the color and depth buffer. -- clears the framebuffer
  gl.glClear(GL10.GL_COLOR_BUFFER_BIT | GL10.GL_DEPTH_BUFFER_BIT); 
  gl.glLoadIdentity();
                gl.glTranslatef(0, 0, -5); 
  // Draw our square.
  /* square.draw() */
  
 }
This code will create a blank frame with black color. We will see the actual drawing code in the part 2. So stay tuned!

Tuesday, September 14, 2010

Add dictionary support to Notepad++

I love Notepad++. It's light-weight, support many languages, has word completion feature and also includes a Spell Checker. So for all practical purposes, it's a functional editor. Having a dictionary support in your editor is always the best thing and it's very simple when it comes to Notepad++. 

It already has a plugin for Spell Checker which you can find under Plugins->Spell Checker ..
All it requires is GNU Aspell and  a dictionary installed on your machine. 
GNU Aspell is a Free and Open Source spell checker. It can either be used as a library or as an independent spell checker. Main features include 
  • possible suggestions for misspelled words 
  • supports UTF-8 document encoding
  • supports multiple dictionaries. 
Enable Spell checker in four easy steps - 
    1. Download and install Aspell for Windows from http://aspell.net/win32
    2. Now install a dictionary which you can download from the same website.
    3. Notepad++ requires a relative path for aspell-15.dll. Open Plugins->Spell Checker.. A dialog box will open where you can edit the relative path. I have both Notepad++ and Aspell installed in "C:\Programs Files" so I entered the path as "../Aspell/bin"
    4. Restart Notepad++

Bingo! Now if you open Spell Checker, it will show you the list of misspelled words in the current document and possible suggestions. 


Friday, September 3, 2010

Add git branch to bash prompt

If you use git, you will find this small trick very useful.

To make your bash prompt super spiffy (and equally useful), add this to ~/.bashrc:

 #Adding git branch to command prompt
 gitStatus() { git diff --quiet 2> /dev/null || echo ' *' ; }
 gitBranch() { git branch --no-color 2> /dev/null | sed -e '/^[^*]/d' -e "s/* \(.*\)/ > \1$(gitStatus)/" ; }

Then, somewhere in your $PS1, put \$(gitBranch). Here's an example; try it:

      export PS1="[\u@\h$ \w\$(gitBranch)]\$ "

When you're in a git directory, you'll notice the branch name on the prompt. If the branch has been modified, an asterisk will appear next to the name. Here is an example :

My command prompt looks like this - 

cdump@cdump-linux : /workspace/android/platform > cros-wm *$

indicating I am on cros-wm branch and there are modified files.

Git-goodness!
Credit Serban Giuroiu

Tuesday, April 20, 2010

Android Application Launch Part 2

There are three distinct phases of process launch :
  1. Process Creation
  2. Binding Application
  3. Launching Activity / Starting Service / Invoking intent receiver ...
Process Creation -

ActivityManagerService creates a new process by invoking startProcessLocked() method which sends arguments to Zygote process over the socket connection. Zygote forks itself and calls ZygoteInit.main() which then instantiates ActivityThread object and finally returns pid of newly created process.
ActivityThread then starts the message loop by calling Looper.prepareLoop() and Looper.loop() subsequently.

The following sequence captures the call sequence in detail -

Application Binding -

The next step is to attach the process to the specific application. This is done by calling bindApplication on the thread object. This method sends BIND_APPLICATION message to the message queue. This message is retrieved by the handler object which then invokes handleMessage() method to trigger the message specific action - handleBindApplication(). This method invokes makeApplication() method which loads app specific classes into memory.

This call sequence is depicted in following figure.

Activity Launch -

After the previous step, the system contains the process responsible for the application with application classes loaded in process's private memory. The call sequence to launch an activity is common between a newly created process and an existing process. The actual process of launching starts in realStartActivity() method which calls sheduleLaunchActivity() on the application thread object. This method sends LAUNCH_ACTIVITY message to the message queue. The message is handled by handleLaunchActivity() method as shown below.
Assuming that user clicks on Video Browser application. the call sequence to launch the activity is as shown in the figure.


The Activity starts its managed lifecycle with onCreate() method call. The activity comes to foreground with onRestart() call and starts interacting with the user with onStart() call.


Android Application Launch

I was part of Android Performance team at Qualcomm and I was working on optimizing the application launch time on Android platform. The first step was to understand the app launch process in detail. Here are some results -

Android Applications are different than standard mobile applications in two major ways.
  1. Every Android application lives in its own world, meaning it runs in a separate process, has its own Dalvik VM instance and is assigned a unique user ID.
  2. Android apps are composed of different components and they can invoke the components owned by other apps. Typically, they don't have a single entry point like main() method.
Application components include :
  • Activities : Encapsulation of a particular operation, optionally associated with GUI, provide an execution context.
  • Services : Background tasks that run in the context of application process.
  • Broadcast Receivers : Broadcast Intent listeners
  • Content providers : Data storage and sharing interface of an app.
Android process is same as Linux process. By default, every installed .apk runs in its own Linux process. Also by default, there exists 1 thread per process. The main thread has a Looper instance to handle the messages from the message queue and it calls Looper.loop() in its every iteration of run() method. It's the job of a looper to pop off the messages from message queue and invoke the corresponding methods to handle it.

When does a process get started? The short version is a process get started whenever it is required. Any time a user or some other system component request the component (could be a service, an activity or an intent receiver) belonging to your apk be executed, the system spins off a new process for your apk if it's not already running. General processes remain running until killed by the system. The point is, processes are created on demand.
For example, if you click on a hyper-link in your e-mail, the web page opens in a browser window. Your mail client and the browser are two separate apps and they run in their two separate processes. The click event causes Android platform to launch a new process so that it can instantiate the browser activity in the context of its own process. The same holds good for any other component in an application.

Let's step back for a moment and have a quick look on the start-up process. Like the most Linux based systems, at startup, the bootloader loads the kernel and starts the init process. The init then spawns the low level Linux processes called "daemons" e.g. android debug daemon, USB daemon etc. These daemons typically handle the low level hardware interfaces including radio interface.

Init process then starts a very interesting process called 'Zygote'. As the name implies it's the very beginning for the rest of the Android platform. This is the process which initializes the very first instance of Dalvik virtual machine and pre-loads all the common classed used by the application framework and the various apps. Then it starts listening on a socket interface for future requests to spawn off new vms for managing new app processes. On receiving a new request, it forks itself to create a new process which gets a pre-initialized vm instance.
After zygote, init starts the runtime process. The zygote then forks to start a well managed process called system server. It starts all core platform services e.g activity manager service and hardware services in its own context. At this point the full stack is ready to launch the first app process - Home app which displays the home screen.

So many things happen behind the scene when a user clicks on an icon and a new application gets launched. Here is the full picture :


The click event gets translated into startActivity(intent) call which gets routed to startActivity(intent) call in ActivityManagerService through Binder IPC. The ActvityManagerService takes couple of actions -
  • The first step is to collect information about the target of the intent object. This is done by using resolveIntent() method on PackageManager object. PackageManager.MATCH_DEFAULT_ONLY and PackageManager.GET_SHARED_LIBRARY_FILES flags are used by default.
  • The target information is saved back into the intent object to avoid re-doing this step.
  • Next important step is to check if user has enough privileges to invoke the target component of the intent. This is done by calling grantUriPermissionLocked() method.
  • If user has enough permissions, ActivityManagerService checks if the target activity requires to be launched in a new task. The task creation depends on Intent flags such as FLAG_ACTIVITY_NEW_TASK and other flags such as FLAG_ACTIVITY_CLEAR_TOP.
  • Now, it's the time to check if the ProcessRecord already exists for the process.
If the ProcessRecord is null, the ActivityManager has to create a new process to instantiate the target component.

(Continued in part2...)

Monday, April 19, 2010

OSome Months ...

Days 3, 4 and 5 were equally eventful and I started the "OSome" week with great enthusiasm. I realized that recording daily events was soon going to be monotonous. It was like this :
while(1) {
code();
debug();
}
on receiving INT_SLEEP : sleep_for_a_while();

Never thought that I would regret a single decision of my life for more than 2 semesters. For some stupid reason, I decided to keep my Spring 2009 semester as light as possible. 2nd mistake. I dropped 15-410 without attending even a single class. 3rd mistake. I hardly spent time at INI during my first semester. 1st mistake. So I hardly knew anyone and I thought I would never get a partner for OS projects. For next two semesters, all I could hear was how great OS was, how people got internships/job only because they did OS and blah... There was a time; I started venerating these special people and it kinda gave me a complex. And finally, I decided not to runaway from this challenge but to face it. I had the golden opportunity where I could have graduated in Dec 2009, could have escaped the snowstorm, 4 months at the haunted house and could have "begun" my married life with my beloved but I had promised myself to rectify those "3 mistakes of my life". I knew I was getting into self-invited mental torture and sleepless nights just to compensate my "last-sem" frame of mind.

15-410... the 5 digits are probably fused in my brain forever. This time I was lucky with the partner. I casually asked one of my juniors (not-so-casually, I was impressed by his ES performance) and he immediately agreed. Well, he was saying yes to his ES TA so it was a perfect win-win situation :)

What's so great about 15-410? 15-410 - Operating System Design and Implementation - the course describes itself as "An experience like no other". Most people say it's a C course.. meaning it's an achievement to get a "C" in the course and it requires a hell lot of effort to get a B and an A is possible only if you are as smart as the CS undergraduate students here. Prof David and his teaching style is at the kernel of the success of this unparalleled course.

So the course began with simple ( most certainly didn't seem simple back then ) labs. The first one was stack crawler to traceback the function calls which was just a warm up exercise as says the handout. Then we wrote some device drivers for keyboard, console and timer and a small game, which gave us a hint of kernel programming. It was just a tip of iceberg! So far so good...

Along came P2 ... the first team project in OS. our own version of POSIX thread library. We had 2 weeks to complete this project. My partner and I manged to evade meeting each other for more than 1 week. Those were the days, when the snowstorm hit Pittsburgh and blanketed the region with a thick white coating and CMU, very reluctantly, closed all classes for 3 days. I was enjoying the snow and had no motivation to work with creeping simics from home. But finally we met, had the stack diagrams ready. I started with mutex implementation and he started with thread_fork(). We gradually conquered the further hurdles such as condition variables and thread_join() and just few hours before the midnight we nailed it. We were jumping with excitement when all test cases returned "END__SUCCESS". We actually worked only for 3 days, which was an achievement! It gained us a lot of respect from peers who thought we would never do it so gracefully.

We were all set to repeat our success story in P3 ... a preemptible multi-threaded kernel from scratch ! a 6 weeks project which carries 25% grade. To keep up the momentum, we started on day 1 !!! First things first, we set up a git repository; we had learnt our lesson during p2. What's next? We read the handout (39 pages) twice but still quite clueless. In other words, we didn't do anything. There comes the checkpoint 1. We missed it by small margin. In TA's words "we were 2 days behind the schedule". Good enough by our standards. The next week was spring break and we both were out of Pittsburgh. The enjoyment ended only to realize that we had missed the checkpoint 2 by a large margin. This time we were 1.5 weeks behind the schedule . Obviously we didn't write a single line of code ... Here after, things began to take a nasty turn.

More in my next post...
(It's 2am right now and I'm still not feeling sleepy. Thanks to 15-410 and my partner who kept me awake through those sleepless nights :P)

Thursday, March 25, 2010

Day 2 - Career Plan

It was raining all day so I decided to stay at home. I cooked my favorite dish 'Alu Palak' which turned out to be delicious as usual :) Today was special because I attended a class on Entrepreneurial Business Planning. Prof Cynker is awesome. I thought I should do an MBA someday in future. A simple day but it gave me a different perspective!

Wednesday, March 24, 2010

Day 1 - Checklist

CMU: List of Things to Do was a good place to start my mission. The first bullet says "Paint the fence" and yes, I have done it twice :) It is an achievement and a moment of pride for every CMUer. Once on Independence day in 2008 when we painted the fence in tricolor

and once more when we "created" the fence at Qualcomm, San Diego during last summer. :)

I started my day with great enthusiasm though I missed my OPT session which was my bad. I then headed to Hamerschlag Hall to meet an alum who works for Lockheed Martin. They had technology day at cmu. Their missiles demo was fascinating. After finishing DS demo Shreyas (ubuntu) and I visited steam tunnels entrance. Well, going down the steam tunnels is not a good idea so we stopped pretty much at the entrance. Checked!
Enjoying sunny and warm weather sitting on lawns and watching a tennis match without worrying about assignments, a dream come true! I finished one more DS demo and went to Hunt library to check out some books on (wait for it) interior decoration :)
And then it finally happened! I had been planning to join Group X classes since my day one but procrastination was the biggest hurdle to pass. Today I did Steps/Weights/Abs class and had real fun. I had every reason to reward myself with homemade egg white sandwich and carrot juice :)


50 Days at CMU : Prologue

I know I started this blog to talk about technical stuff but more on that later.
Yesterday I suddenly realized that I had only 50 days left at CMU. I had never felt a real sense of attachment with CMU or INI until this very thought struct my mind. I am feeling sad now. I have missed out on Algorithms course, some very interesting courses like Intro to Magic, Professional Baking class and Rubik cube and so on and all GSA activities :( But now I have promised myself to enjoy the last 50 days at Pittsburgh. I am gonna do something new and/or interesting everyday and will describe my day here :)

Thursday, February 25, 2010

|| श्री ||

The urge was quite significant to start blogging since a long time but the implementation was inversely proportional to it... Tonight, after finishing my 15-410 midterm, I suddenly find myself with lots of time and here I am; writing my first blog.
So why multi-core-dump? It's very typical to open up a program in gdb after you see a coredump. Whenever I have failed to do something I have always learnt a new thing or at least a new way to do the same thing. I hope to share my learning process without restricting myself to any particular area thus making it multi-threaded on a multi-core CPU ;)