Circular Buffer Problem

A classic problem in operating system is to handle the producer and consumer scenario. Producer will keep producing new data and consumer will consume that data. To do so say the producer and consumer process share the same memory. Lets say the size of that memory shared is fixed or bounded. Can you implement a logic to produce a data to that buffer when space is available. Similarly consumer can read only when data is available and the buffer is not empty.

This can be achieved by a circular bounded buffer shared between the producer and consumer.

/* the size of the bounded shared buffer */
#define BUFFER_SIZE 10

/* Each elements of the buffer */
typedef struct element {
	int i;//some data is present

/* The shared buffer, each index is of the type element */
element data_buffer[BUFFER_SIZE];

Let us come with the logic

Other than sharing the data_buffer, the producer and consumer must share the index where to produce data and from where to consume it.

Let’s define that

/* Add element in position "in" and move to next */
int in = 0; 

/* remove element from position "out" and move to next */
int out = 0;

Now how to know when the buffer is FULL so any element can’t be added. Similarly how to know when buffer is empty when element can be read or consumed. Let’s define the rules

/* if in == out, buffer is empty */

/* if (in + 1)%BUFFER_SIZE == out buffer is full */

Okay now lets write the pseudo code of the producer

/* producer */

while(TRUE) {

        /* keep waiting as buffer is full*/
	while((in + 1)%BUFFER_SIZE == out);
	data_buffer[in] = data_produced;
	in = (in+1)%BUFFER_SIZE;


The consumer pseudo code

/* consumer */

while(TRUE) {

        /* keep waiting as buffer is empty, nothing to consume */
	while(in == out);
	data_consumed = data_buffer[out];
	out = (out + 1)%BUFFER_SIZE;


I hope the above logic is self explanatory. I have a question for you, how many elements will make the buffer full in the above logic ?

Linux Kernel Barriers

Sometimes you need to have the memory read (load) and write operation (store) to be executed in certain order. But it may be that complier (or processor) can reorder reads and writes for performance reason.

It is possible to instruct the compiler not to reorder read or write at a given point. These instructions are called barriers.

Let us take a simple example

x = 1;
y = 2;

On some processors “y” may store new value first before “x”. That is second store instruction above gets executed before 1st store instruction.

But this reorder will never happen if the instructions are related, for example

x = 1;
y = x;

A mb() call provides both read and write barrier. No load and store will get reordered across this barrier.

Thus the below instructions will not reorder now

x = 1;
mb(); /* barrier */
y = 2;

Further Read

Cscope tags with Vim: easy setup

These setup steps will help you to browse code efficiently

Steps :

Install Cscope, if you already have ignore this step

apt-get install cscope

Install cscope plugins

mkdir ~/.vim/plugins
cd ~/.vim/plugins

Add this below line in .vimrc file

source ~/.vim/plugins/cscope_maps.vim

In .bashrc file add these lines. This will create an alias which will search and index the file types as mentioned

alias mycscope='export SB=$PWD;find $SB ( -name '.[chs]' -o -name '.cc' -o -name '.cpp' -o -name '.hh' ) > $SB/cscope.files;cscope -b -q -R -i   $SB/cscope.files'

export CSCOPE_DB

Now go to the top directory of your codebase from where you want to build your cscope.

nirweb:/mysandbox/src$ bash
nirweb:/mysandbox/src$ mycscope
nirweb:/mysandbox/src$ ls -l cscope.out

Verify that cscope.out is created. Now run cscope

cscope -q -d

Browse your codebase using these common shortcuts

Jump to definition

Ctrl + ]

To return back

Ctrl + t

To find all references

Ctrl + \s

Note "+" is not a keystroke, it just indicates the combination

Happy browsing.

Some references

Save time by creating multiple Tabs with Linux Screen in the same window

It is tedious to browse through your linux screen windows, by typing “Ctrl a” + ” every-time you want to switch to another window. A better approach, that will save your time is to use multiple Tabs in the same window. You will remember the context and can quickly switch among the tabs.

So let us quickly get the tabs.

Screen Tabs Setup

Open a terminal and first install screen if screen is not already installed

nir@ubuntu:~$ sudo apt-get install screen
nir@ubuntu:~$ which screen

Open your .screenrc file and add the following string and you are set.

nir@ubuntu:~$ cat ~/.screenrc 
caption always "%{= kw}%-w%{= BW}%n %t%{-}%+w %-="

Note it will work for all new screen session you are creating

Test linux screen with multiple tabs

Let us create a new screen session called myShell

nir@ubuntu:~$ screen -S myShell

Once you are in, you can see already at the bottom
a tab is created named “0 bash”

Create couple more by pressing “Ctrl a” + “c”
You can see more tabs getting created.

To go from one tab to next
“Ctrl a” + “n”

To go from one tab to previous
“Ctrl a” + “p”

To rename a tab use
“Ctrl a” + “A”
(note “A” is in CAPS)

Here is a screenshot of what you will get after executing the above commands

linux screen example
linux screen example

To jump to any tabs you can use the number seen along with the tab
“Ctrl a” + n
where n can be 0,1,2 in the above example.

Switching vs Routing : How to know if a packet will get switched or routed

Given a packet, can you tell, if it will get switched or routed ? What algorithm will you use.

To understand this, let us dig into what happens during switching and routing.

Switching happens in the same network. And routing works across the network.

The fundamental concept for Switching is it works at Layer 2 (L2) and Routing works at Layer 3 (L3) of the networking stack.

For switching to happen L2 lookup is necessary. The L2 data (for ethernet) present in the packet header includes Destination MAC, Source MAC, VLAN etc.

For routing to happen L3 lookup is necessary. The L3 data present in the packet header includes Source Ip, Destination Ip etc.

But when will L3 lookup happen ?

After L2 lookup matches then L3 lookup starts (Similarly, after L3 lookup matches then L4 lookup will start and so on, for the entire network layers)

Switching / L2 Lookup

When the packet arrives on a port, the destination MAC address present as a part of the packet header is matched against the MAC address of the port on which this packet is received.

If the Destination MAC address present in the packet header is same to the MAC address of the port on which this packet is received, the packet has reached its destination when Layer 2 is concerned. The packet can now proceed for L3 lookup.

But what will happen if the packet’s destination MAC does not match with the MAC address of the port on which it is received ?

Then, the MAC address table lookup happens. The MAC address table, is a table that has the following key fields (or columns). Let us take an example

mac address table
MAC Address Table key fields

The above tables tells that MAC aa:00:bb:00:cc:00 is learnt on port 1/1/1 and belongs to VLAN 10. Or in other words, to reach destination MAC aa:00:bb:00:cc:00 use port 1/1/1 as the egress port for all packets part of VLAN 10.

As the MAC is learnt so the type is “dynamic”. On the other hand if administrator configures the above table entry manually then the type becomes “static”.

So when MAC table lookup happens, the destination MAC specified in the packet header matches with an entry in the MAC address table, for the same vlan, then the packet is forwarded to that port. In other words, this is switching.

Routing / L3 Lookup

As discussed above, L3 lookup will happen after L2 match is found – that is when the destination MAC of the packet matches with the mac address of the port on which it is received.

Now it can go ahead for L3 lookup and see if the Destination IP present in the packet header also matches with the IP address of the port where the packet is received. (Or it can be a L3 virtual port as well, example a SVI – switch virtual interface, which is essentially is a L3 VLAN port ).

If the above matches, the packet has reached the final destination. If it does not match, then Routing table lookup happens and the packet gets routed to another network. In other words, routing takes place.

So to answer the question “what decides if a packet will get switched or routed” as you can see it all dependents on the Destination MAC.

So if the packet has not yet reached its destination MAC, switching happens. If packet has reached the destination MAC, it checks to see if routing is necessary.

How does a switch know if a packet is VLAN tagged or untagged

When a packet arrives in the port how does the switch know what is the VLAN tag in that packet. In other words what VLAN does that packet belong ?

In a switch what is received is an ethernet packet. Here is  how a typical ethernet untagged frame looks like (excluding the preamble, crc etc)

Ethernet packet without vlan tag
Figure 1: Ethernet packet without vlan tag

When a packet is VLAN tagged, that VLAN information is also sent in the above Ethernet Frame.

How does the VLAN fit into the ethernet frame? Vlan is part of the .1Q (Dot1Q) header.

The .1Q header is of 4 bytes. It is represented as

Vlan Tag
Figure 2: Dot1Q Header

TPID: Tag protocol identifier. When it is set to 0x8100, it represents .1Q vlan tagged packet.

VID: Vlan Identifier, is a 12 bits representation of vlan.

The entire packet frame with the .1Q header looks like

ethernet packet with vlan
Figure 3: Ethernet packet with vlan tag

This is as per the IEEE 802.1Q (or Dot1q) standard.

The key here is to note the overlap between the frame structure of a normal untagged ethernet packet without any VLAN information and the VLAN tagged packet (Figure 1 vs Figure 3).

You will notice that the ethertype (in Figure 1) and the VLAN tag information (in Figure 3) resides at the same offset from the start of the packet. That is 12 bytes from the start of the packet.

Now when any packet is received by the switch, part of the switching algorithm is to skip the 6 bytes Destination Mac + 6 bytes of Source Mac (i.e total 12 bytes) and read the next 2 bytes.

If the value is 0x8100, which is the TPID as show in the above diagram, then the switch knows that the VLAN tag is present and parses the frame further to retrieve it.

Question for you :-

If an untagged packet is received on an access port, what vlan does that packet belong to ?


Vlan Access Port, explained with Example

Access port in a switch is a port, which is associated with a single VLAN connecting usually to a host. 

Access port in egress (transmit) path will always send untagged packet out.

In ingress (receipt) path, the access port can accept both untagged and tagged packets. But note, not all tagged packets, it is only for that VLAN which is associated with this port.

Note: In some products the requirement may be to only accept untagged packets on access port

Let us take an example to understand it better


In the above diagram it can be seen that host H1(can be a linux host machine) is connected directly to a switch Sw1

Let the port of Sw1 connecting host H1 be an access port of vlan say 10


So if H1 send a packet to Sw1 as untagged ethernet packet, sw1 will accept and it will be treated as a packet belonging to vlan 10.(The Host H1 can remain unaware of the VLAN)

H1(if it is vlan aware) can send a tagged packet with vlan 10 as well and still be accepted by Sw1, as the connecting port in Sw1 is belonging to the same vlan.

However if a packet tagged with vlan 20 arrives Sw1, it will be dropped.


In egress Sw1 will always send out untagged packet for that vlan.

Even if say Sw1 received a tagged packet with vlan 10 from some other port and it needs to switch it out via this port to H1, it will send it out as untagged.

Here is typical diagram involving only access ports


In the above diagram all ports of the switch are access ports of the respective VLANs. VLAN 10 hosts can ping each other and likewise VLAN 20 hosts can ping each other.

But VLAN10 hosts can’t reach VLAN 20 hosts and vice versa.

Question for you

Now that you know what is a access port, I do have a followup question. In the previous example we saw a host connecting a switch via access port. So can we have a switch connecting to another switch via access port ?

Can you think of what are the shortcoming in connecting two switches via access port ?

How to do copy paste in VNC on Mac without any external software or mouse

As a developer you might be using VNC frequently. But new Mac user will find there is no Shift+Insert or middle click option available in Mac. Using these key combinations it is possible paste content in VNC (Windows) but these keys are not present in Mac.

So here is the alternate I use

In the VNC window you will see the Settings tab. Click there you will find Configure Shortcuts.  As in the image below

VNC copy paste shortcut
VNC configure shortcut

If you scroll you will find various option to configure. Click on Paste and select Custom and then click the button next to it to set your  shortcut for paste. In my case I have selected command+v as the shortcut for paste. Similarly you can set command+c the shotcut for copy.

Thus whenever you select any lines on your VNC just click command C to copy and command V to paste it.

However if the above do not work, say if you are working in xterm instead of konsole. Then how can you paste items from clipboard easily ? Usually if you highlight text it gets copied but there is no option to paste without using mouse. If you had a mouse a middle click would have served the purpose. So now without a mouse we need to have some trigger which acts as a mouse middle click. To serve this purpose I use MagicPrefs.

Install MagicPrefs. Once done it appears in the top menu, as you can see in the picture below

Screen Shot MagicPrefs in Menu bar

Now Click, MagicPrefs->Prefences, it open up

Screen Shot MagicPrefs Preference

Set the 3 finger click middle click option. That’s it. For a quick test open your terminal from dock (or VNC) highlight any text (gets copied in clipboard). Now do a 3 finger tap to paste.

If this was helpful to you, please share and let me know your comments below.