Recursive Complexity

Thoughts and musings of a programmer and wanna be entrepreneur

Array indexing in C, the unknown kind

with one comment

int a[5] = { 1, 2, 3, 4, 5 };

printf(“%d\n”, a[3], 3[a]);

output: 4, 4 -> Holy crap! I didn’t know that. I tried it out on the latest version of GCC and it works. Surely, C is like a sea.

Written by Vivek S

June 7, 2012 at 11:14 am

Posted in Tech

Tagged with , ,

Linux Socket Calls and What Happens Internally

with 2 comments

This post is the result of my own curiosity and need to find out how data sent by user space applications like ping and telnet reach a suitable network device on the system which then sends it across the network. The material in this post solely concerns the path data takes from user space to kernel space and finally the network device and not beyond that. Although most of this material is obtained by digging into Linux kernel source code, the logic might apply to Windows and other operating systems as well.

A short note on Linux system calls


In Linux most of the heavy lifting of the system calls is handled by the GNU C library glibc which contains wrappers for these system calls. What the user calls is actually a library function and not the system call itself. This provides the advantage of not having to worry about any changes in the system call interface as it’s the library that has to change and not the user program. In Linux, each system call has a unique identifier associated with it (__NR_syscall) which can be found in /usr/include/asm-generic/unistd.h on any Linux installation. This can be a little misleading though as the below paragraph summarizes the issue. This system call identifier is placed in AX register and the parameters to the syscall are placed in other registers and the assembly instruction syscall or sysenter is executed which transfers control to the kernel which then based on the syscall identifier executes the appropriate kernel function. In older systems, a software interrupt 0x81 used to be issued to transfer control to the kernel during a system call. This has been replaced now by the above instructions and this keeps changing when more efficient methods are discovered to do the same.

The system calls related to socket API’s are tricky to figure out as there isn’t a direct relation to the glibc syscall wrapper and the kernel function that gets called. This is the case on 32-bit architectures. All socket system calls are multiplexed into a single kernel function called sys_socketcall defined in net/socket.c (as is all other socket system calls). This function takes as its first parameter, the sub-function identifier that identifies the appropriate function that needs to be called. This function acts as the entry point for all socket system calls on 32-bit architectures as far as I know. On 64-bit architectures this is not the case and each glibc library function calls the relevant system call directly.

Socket API’s behind the scenes.


We will take a look at two functions, socket() and connect(), that should lay the foundation and make it easy to follow what happens when other functions are called.

int socket(int domain, int type, int protocol)

The very first thing an application does to enable itself to communicate across the network is to create a socket. There are three parameters passed to this function, the domain of the socket which also happens to be the protocol family (AF_INET, AF_INET6, AF_UNIX etc), the type of the socket (SOCK_STREAM, SOCK_DGRAM, SOCK_RAW etc) and the protocol (generally 0 or the protocol number that is supported by the communication domain/protocol family) that would be used to communicate using the socket. This function returns a file descriptor that describes the socket (in Linux everything or almost everything is a file) that is created on successful completion. The glibc library function socket invokes the sys_socketcall kernel function on 32-bit arch or sys_socket kernel function directly on 64-bit arch. Nonetheless, sys_socket is the final destination for the socket system call.

Now lets see what happens in sys_socket kernel function. Based on the protocol family/domain, it chooses the net_proto_family structure that describes this protocol. The pointers to these structures are stored in the global array net_families[] in file net/socket.c. Every protocol driver when it loads, registers its protocol with the kernel which then updates this array to reflect support for this protocol. After obtaining a pointer to the appropriate protocol handler, it calls the create function present inside the structure. This for AF_INET/PF_INET is the inet_create function in file net/ipv4/af_inet.c. Each socket type can support multiple protocols which can be obtained from the array of inetsw and the socket type passed to the socket system call. This list is then iterated in the inet_create, function matching the protocol passed to the system call with the protocol supported by each item in the list. For AF_INET family inetsw_array[] contains all the socket type and protocol combination it supports. If there is a match, then the socket operations is assigned to the operations supported by the handler, the socket protocol is assigned to the protocol of the handler and the control returns to sys_socket.

Next, sys_socket calls sock_map_fd to allocate a file descriptor and make it represent the socket. This function in turn calls sock_alloc_file which gets an unused file descriptor to represent a file, creates a file, assigns the created socket as the private data for the file. It also assigns socket_file_ops structure as the file operations. The control is then returned to sys_socket which return the created file descriptor to user space.

int connect(int sockfd, const struct sockaddr *addr, socklen_t addrlen);

The connect socket function establishes a connection to the peer identified by the sockaddr structure pointer passed as the second parameter. The first parameter is the socket file descriptor obtained by calling function socket. The last parameter is the size of sockaddr structure. The system call related to function connect is sys_connect defined in file net/socket.c. The very first thing the sys_connect function does is to lookup the file descriptor that represents the socket using function sockfd_lookup_light. This function searches the kernel file descriptor table for the file that represents the socket and returns it. The private data of the file contains a pointer to structure socket as mentioned above in the description for socket system call which is returned to function sys_socket. Then the user space address of sockaddr is moved to kernel space and the connect function of the socket operations is called. This for socket family of AF_INET and socket type of SOCK_STREAM, points to inet_stream_ops->connect. The structure socket obtained contains a pointer to structure sock which is the network layer representation of the socket. Using this pointer, a call is made to sk->sk_prot->connect which for ipv4 stream ops happens to be tcp_prot->connect which is tcp_v4_connect. These pointers are already assigned during socket creation time (see above explanation of the creation of a socket). tcp_v4_connect calls ip_route_connect which consults the kernel routing table to figure out the device that should be used for the connection and using this information tries to establish a connection to the peer and returns the result back to the user.

The above description is just an overview of how socket creation and connection establishment works inside the Linux kernel. This is a complex mechanism with a lot of protocols and drivers involved and needs patience and constant effort to understand as there is very little documentation. Digging through the kernel is probably the best way to figure out things as is with many other things related to the kernel.

Written by Vivek S

June 4, 2012 at 9:54 am

Posted in Tech

Tagged with , ,

Rangashankara

leave a comment »

Today I was for the very first time introduced to the world of theatre. It was a very wonderful experience and I must thank my friend Sahana for that. I had never been to any plays before and hadn’t thought of attending one either. I must admit that it is really nice. The play we sat for was called “Naanu thukaram alla” (it’s in Kannada) and belonged to the genre of comedy mixed with some seriousness here and there.

Over the past few months, weekends were getting very boring and I couldn’t think of things to do. I wanted a new perspective and a new heading. I guess this is what I was looking for and hope this gives me the required impetus to look at different, better and more beautiful things that can give a whole lot of satisfaction and happiness. It’s good to have someone who can help you out in this endeavour and I thank Sahana for it again.

Looking forward to more entertaining and fulfilling time at Rangashankara in the future and not to mention the “akki rotti” you get to taste after the play gets over.

Written by Vivek S

December 11, 2011 at 3:00 pm

Posted in Leisure

The smartphone and the cloud…few possibilities (part 3)

leave a comment »

This is the 3rd article in a series of 3 articles talking about the use of the cloud for the smart phones. The previous 2 articles can be found here and here.

In this article I talk about how the cloud can be used to extend the storage space available to a smart phone. Smart phones of today and in the near future typically have/will have a storage space big enough to store lots of data. If you want to store lot of movies and want them readily available for viewing on your smart phone, you can store those movies locally. But that would consume vital disk space that can be used for apps or other more useful data (considering that movies are not that useful and only serve as entertainment 🙂 ).

Devices on the cloud typically have some local storage space. Now, can we use the storage space available on those devices in order to store and retrieve data ? Yes we can and the technology required would also be simple and an extension of what is already there for desktop and server systems.

Remote storage area

In the above figure, the smart phone accesses the storage space available on another smart phone, desktop, laptop or storage device that forms part of the cloud. These device that offer storage space need to have some kind of hardware or software support that enables another device on the cloud to access them and request for use of their storage area. The smart phone that accesses this storage space makes it appear as a local storage area for the user. All data transfer to and from this remote storage space is made just like it would happen for data transfers to and from local storage area. The lower levels of the smart phone operating system would take care of the steps required to send and receive the data to the remote storage area.

The concept is the same as the iSCSI, FCoE and FC technologies that enable desktop/laptop/server systems to login to and access disk area present on a remote system which is accessible. A target system has a software running on it which listens for in coming requests to access the storage space and after authenticating the requests provides permission to access the storage area. The client making the request is known as the initiator. This initiator target concept originates from SCSI protocol.

Although this process is network intensive and consumes a lot of bandwidth, it is assumed that in the future the network would we very fast and free of any glitches which makes this idea very viable.

Prerequisites

  • Hardware or software support to make the remote storage space available for clients.
  • Hardware or software support on clients to access the remote storage area.
  • Fast networks.
  • Secure networks.

Advantages

  • The smart phone may become entirely diskless. All data can be sent to and accessed from this remote storage area.
  • Critical data my be stored on other remote devices which provides redundancy and data loss protection.
  • Data can sent from one device to the other without much effort. This for example can help the user to download a move on his mobile phone and store it on his desktop. When he/she returns home, can view it easily on his/her desktop.
  • No need for mobile devices to support huge storage devices.
  • The mobile devices can become smaller and more portable as less space storage devices occupy less space.

Disadvantages

  • The remote device that provides access to the storage area has to be running all the time. This consumes a lot of power.
  • Security is a problem as eaves dropping and spoofing are common on public networks.
  • If the network is slow, it’s a pain to wait till all data is transferred.

The smart phone in the future will be a full-fledged computing device and the network will have many more capabilities added to it repertoire. Hence, the ideas talked about in this series make sense and will be available to the user soon. This ends my 3 article series. Hope you enjoyed it :-).

Written by Vivek S

July 16, 2011 at 8:58 am

Posted in Tech

Tagged with , ,

The smartphone and the cloud…few possibilities (part 2)

with one comment

This is the second article in a series of 3 articles, about the use of the cloud for the smart phone.

As I mentioned in my previous article, the cloud can be used to bring up a mobile phone, saving memory occupied by the OS along with many other advantages as mentioned in that article.

Now let us take it a bit further and make the mobile phone boot off of another mobile phone, laptop, desktop or a storage device that is part of the cloud.

Boot from another storage device

Cloud boot

When the user switches on his mobile phone, a ROM embedded in the device is loaded in main memory. This ROM then initializes the network stack and establishes a connection to the cloud. This connection establishment is actually to the individual device which contains the boot image. However, for the end user, he is just establishing a connection to the cloud. The protocol used to establish the connection and make a request for the boot image should contain some facility to specify whether the boot image is located on a particular device or in the data center. Based on this parameter, the  cloud internally establishes a connection to this device and requests it to deliver the required boot image. This boot image is then forwarded to the end user. The protocol used inside the cloud may be entirely different from the one used for the communication between the end user and the cloud or the same, whichever is safe and convinient.

Pre-requisites

  • Special software (embedded ROM) or hardware support for the boot process in the device that serves the boot image.
  • The individual device on the cloud should be up and running.
  • Secure access to the boot image from the user to the cloud.

Advantages

  • No need for data centre access which might cost money.
  • Mutlitple mobile phones, but just one OS image is necessary. This saves cost as the user has to pay for an OS image.
  • Customized OS to suit the user need.
  • One place upgrade of OS components.

Disadvantages

  • The device needs to be up and running when the request for the boot image is made.
  • Secure access to individual devices is a tricky business as it has to be done by the person owning the device. In a data center, security is a given as people pay for the services. In this scenario, there is no money involved.
  • Special software (embedded ROM) or hardware support for the boot process on the individual devices.

This process serves a back up for the one described in my previous article. When there is no access to the data center, the user can boot his mobile phone from a nearby laptop or a desktop provided he/she has set it up to provide the boot image.

Written by Vivek S

July 3, 2011 at 5:05 pm

Posted in Tech

Tagged with , ,

The smartphone and the cloud…few possibilities (part 1)

with one comment

This is the first article in a series of 3, discussing applications of the cloud for the smartphones of the future not far off.

In this article, I will discuss booting a smart phone off the cloud.

The ideas presented in this series can be debated and have drawbacks, but I am sure this is the direction the smartphones are headed. The desktops and servers of today are already there and the next step is for the mobile phones to do the same.

I use the term smart phone assuming that all mobile phones of the future will be smart enough to interact with the cloud.

Boot is a term widely used for computers and as I am unaware of the term used to bring up a mobile phone, I will use the same here.

Booting a smart phone off the cloud.

Smartphones of today have the operating system (OS) image stored in permanent memory that comes along with them. When we power on a smart phone, the OS image is loaded into main memory (RAM), the control is transferred to it, after doing some necessary initialization and error checking and the phone starts to boot. Imagine a scenario where the OS image is stored in the cloud, in data centers and when we power on the smart phone, it requests the desired image from the cloud which is then provided to it by the cloud. See figure below.

Booting a smart phone from the cloud

Prerequisites for this process would be,

  • A ROM burned into the device that can communicate with the cloud.
  • User/client specific access to data stored on the cloud.
  • Security against snooping, hacking and other malicious activities.

The steps for the process would be,

  • The smart phone is powered on by the user.
  • The ROM is loaded into main memory and given control.
  • It establishes a secure connection to the cloud.
  • A request for the user OS image is made.
  • The cloud finds the user specific OS image by communicating internally.
  • The cloud then securely responds to this request.
  • The OS image is downloaded to the smart phone and then loaded into main memory and given control.
  • The phone starts to boot.
  • After the user is done using the phone, he powers off the phone.
  • A background process initiates a ‘save all changes’ session to the cloud.
  • All changes made to the OS and its application are saved to the cloud.
  • The device powers off.
  • The next time the user powers on the device, the updated OS image is provided.

As mobile phones are used by almost everyone today including me :-), a scenario observed is that we never switch off our phones. So when do the changes get committed to the cloud ?

An answer to this would be to have the back ground process save the changes, if any, at regular intervals, which the user can customize.

This idea is merely an extension of what is already there for desktop and server systems. Technologies like PXE, iSCSI, FC and FCoE are widely used in SAN environments to remotely (diskless) boot computers. The same technologies adapted to portable devices or new technologies based on them may be brought forward to achieve remote boot of mobile phones.

Advantages

  • If a mobile phone is lost or damaged, data is still present on the cloud. No need to worry about data loss.
  • Data centers have advanced backup facilities that cannot be replicated by the user.
  • One place upgrade of OS and other applications which serves all clients.
  • Saves storage space previously occupied by the OS.

Disadvantages or drawbacks

  • Security is a major concern as is with all things associated with the cloud.
  • Cannot boot a mobile phone if there is no access to the cloud as can happen in remote places.
  • Slow network speeds can make the boot process a terribly long wait.

Given that networks all over the world are becoming more secure and everything is moving to the cloud, this seems to me to be a logical step for the smart phones of the future.

Written by Vivek S

June 26, 2011 at 10:56 am

Posted in Tech

Tagged with ,

Why Roger Federer loses to Rafael Nadal

leave a comment »

1. Roger Federer is far less tough in his mind than Rafael Nadal. Don’t get me wrong here. He’s tougher than everyone else but Nadal. There is no one on the planet who fights like Nadal.

2. Roger Federer plays a toned down game of grass court on clay where he tends to hit the ball on the rise and with pace which doesn’t help his cause at all. Clay court requires a totally different game than grass or hard court.

3. Most important of all, Federer plays Rafael Nadal, his tormentor rather than playing the ball. Nadal’s in his mind and he plays him, rather than playing the match like any other!

The finals of French Open was a brilliant game. This was Federer’s best French open and Nadal came through to win even though he wasn’t playing his best tennis. So there are positives for both the players. Federer got it right when he started the match. He seemed to have a plan. He played aggresively and was in no time up 4-1. Then everything went down. Nadal got some rhythm and started to get Federer’s tactics. The problem for Federer is that I don’t think he has a plan B. If he doesn’t get it right the first time, he struggles. Tactically Nadal is brilliant. He approaches every game as though it is his last. It’s also so amazing to see Nadal learn the grass court and hard court games so quickly whereas Federer has not been able to do the same on clay.

On the whole, it was a brilliant game of tennis and I wonder how many more days are left before this great rivalry comes to an end given the fact that Federer is nearing the end of his career. Till then feast your eyes on those wonderful moments in the history of this game when they both played magical tennis (Wimbledon finals 2007 and 2008, Australian open finals 2009). Two greats of the game.

Written by Vivek S

June 7, 2011 at 4:59 pm

Posted in Tennis

Tagged with , ,

TED Blog

The TED Blog shares interesting news about TED, TED Talks video, the TED Prize and more.