Why linux keeps connected routes when link goes down?

I came across this interesting discussion on a particular behavior of linux. This issues was brought up by a system administrator who was facing an interesting situation. When the link of an interface goes down possibly due to hardware failure or cable pull out, the ip address and routes associated with that interface is retained until someone explicitly deletes it. This behavior is built into linux for more than 10 years and the reason for this was stated by David Miller.

The default behavior for a general purpose operating system is
to increase the likelyhood of successful communication.

And the way to maximize successful communication is to associate
addresses with the host rather than the interface.

It becomes clear why the developers decided to go with associating ip address with a particular node rather than an interface in the node. The problem with this implementation is relevant when linux is being used as a router. A router is a multi-homed host and tends to have multiple interfaces each connected to different network. So if a situation arises where the router finds a route entry to send a particular packet there are chances that the link may be down and packet never reaches the destination. Even if there are alternated routes to reach the particular destination it cannot be used as there is already an existing valid route with a interface that is down. Lennart Sorensen argued against David Miller's claim that different interface of the router might be connected to same network in which case the alternate interface can be taken. According to Lennart it still useless as we would end up having 2 route entries to the same destination with different interfaces and would pose the same problem when the first route entry points to an interface which is down. The no conclusion to this little problem as David points out in his replay to Lennart.

This decision was made at least 10 years ago, and if you think what we
have now is broken just imagine how much struff would explode if we
changed things.

All is not lost in this regard for people using linux as router. Stephen Hemminger suggested using quagga for this purpose. There are patches submitted to the quagga mailing list which does what Lennart wants without any modification to the kernel behaviour. Unfortunately those patches are not yet upstream in the quagga branch and has to be applied as patch. So in future would quagga become the routing management daemon for linux? Thats something we need to watch out.

Theory Behind Hiding Zipped File Under Jpg Image

The post Hiding Zipped File Under Jpg Image showed the steps to achieve data hiding in jpg. Since Ego was questioning the theory behind this, i decided to get my hands dirty and find the answer. To understand this, we need to understand the data structures of jpg image and zip files.
Lets bisect the jpg image first.
Jpg Header Format:

Start of Image (SOI) marker -- two bytes (FFD8)
JFIF marker (FFE0)

  * length -- two bytes
  * identifier -- five bytes: 4A, 46, 49, 46, 00 (the ASCII code equivalent of a zero terminated "JFIF" string)
  * version -- two bytes: often 01, 02
        o the most significant byte is used for major revisions
        o the least significant byte for minor revisions

  * units -- one byte: Units for the X and Y densities
        o 0 => no units, X and Y specify the pixel aspect ratio
        o 1 => X and Y are dots per inch
        o 2 => X and Y are dots per cm
  * Xdensity -- two bytes
  * Ydensity -- two bytes
  * Xthumbnail -- one byte: 0 = no thumbnail
  * Ythumbnail -- one byte: 0 = no thumbnail
  * (RGB)n -- 3n bytes: packed (24-bit) RGB values for the thumbnail pixels, n = Xthumbnail *
     Ythumbnail

The bold words in the above header is of importance to us. The 4 byte value consisting of SOI and JFIF marker. This signifies the starting of the jpg image. Any standard image viewer searches the file for "d8ff e0ff" (little endian mode) pattern. Once this of found, marks the start of the jpg image. The end of the jpg image is marked with "0xd9ff" (little endian mode). A cat on the image is going to make sure that some data is written after 0xd9ff there by making it unnecessary for any image viewer to bother about data after 0xd9ff.

Lets look at the zip header format.
Overall .ZIP file format:

[local file header 1]
[file data 1]
[data descriptor 1]
.
.
.
[local file header n]
[file data n]
[data descriptor n]
[archive decryption header]
[archive extra data record]
[central directory]
[zip64 end of central directory record]
[zip64 end of central directory locator]
[end of central directory record]

The one that concerns us is local file header

Local file header:

local file header signature 4 bytes (0x04034b50)
version needed to extract 2 bytes
general purpose bit flag 2 bytes
compression method 2 bytes
last mod file time 2 bytes
last mod file date 2 bytes
crc-32 4 bytes
compressed size 4 bytes
uncompressed size 4 bytes
file name length 2 bytes
extra field length 2 bytes

file name (variable size)
extra field (variable size)

As seen in the bold letters is the signature of the start of the zip file. So the unzip program tries to find the above pattern in the file and assumes that the rest of the file till "end of central dir record" is reached. This explains why tar.gz or tar.bz2 files don't work while zip does. In other words, the gz/bz2 formats look for starting 4 bytes as identifiers and if not found will quit immediately.
The following example will illustrate the file layout of the various file formats.
Example: Generated using hexdump
Image file (jpg):

0000000 d8ff e0ff 1000 464a 4649 0100 0001 0100
0000010 0100 0000 dbff 8400 1000 0c0b 0c0e 100a
.
.
0005b50 4792 d9ff
0005b54

As discussed, the hex value in bold indicates the start of the jpg file. Now lets look at the zip file.
Zip file (.zip):

0000000 4b50 0403 0014 0000 0008 776b 3a41 d8d9
0000010 00d8 1109 000c 2c00 000d 0009 0015 6f77
.
.
00c1190 0100 0100 4400 0000 4500 0c11 0000 0000
00c119f

After the concatenation, the file now consists of both jpg and zip content as shown below.
Embedded Image File (jpg):

0000000 d8ff e0ff 1000 464a 4649 0100 0001 0100
0000010 0100 0000 dbff 8400 1000 0c0b 0c0e 100a
.
.
.
0005b50 4792 d9ff 4b50 0403 0014 0000 0008 776b
0005b60 3a41 d8d9 00d8 1109 000c 2c00 000d 0009
.
.
00c6ce0 0006 0000 0100 0100 4400 0000 4500 0c11
00c6cf0 0000 0000
00c6cf3

This little example must be able to clear out the doubts of how this works. Next step would be to manipulate the hex file to make zip program believe that jpg data is the zipped data. Stay tuned for more on this.

Hiding Zipped Files Under Jpg Images

Sometimes we come across situations when we have to hide certain files. There are many methods in which this can be accomplished. This is one of the many ways to do so. This applies to only zip file contents.

Step 1: Zip the file/folder to be hidden

#zip xyz.ppt.zip xyz.ppt

Lets assume that abc.jpg is the image we are using for the camouflage.
 
Step 2: Hide the zipped contents

#cat abc.jpg xyz.ppt.zip > new.jpg

The new.jpg will be jpg file that hides the zipped content. The file will have meta data as jpg and any image viewer will be able to open it.

To extract the hidden contents:

#unzip new.jpg

Vola!! Thats it. Its as simple as it is! Thanks to Naveed for this tip.

Sample Code To Learn Netlink Infrastructure

I always wanted to write an article explaining how netlink infrastructure works in the kernel and how we can make the best use of it. I dont have the time now, so in future it will happen. As of now i wanted to share a sample code that will help users get the system ip information to the user space.

#include <errno.h>
#include <error.h>
#include <netdb.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <netinet/in.h>
#include <sys/socket.h>
#include <sys/ioctl.h>
#include <linux/if.h>
#include <linux/netlink.h>
#include <linux/rtnetlink.h>


#define NIPQUAD(addr) \
        ((unsigned char *)&addr)[0], \
        ((unsigned char *)&addr)[1], \
        ((unsigned char *)&addr)[2], \
        ((unsigned char *)&addr)[3]

#define NIPQUAD_FMT "%u.%u.%u.%u"

#define NIP6(addr) \
        ntohs((addr).s6_addr16[0]), \
        ntohs((addr).s6_addr16[1]), \
        ntohs((addr).s6_addr16[2]), \
        ntohs((addr).s6_addr16[3]), \
        ntohs((addr).s6_addr16[4]), \
        ntohs((addr).s6_addr16[5]), \
        ntohs((addr).s6_addr16[6]), \
        ntohs((addr).s6_addr16[7])

#define NIP6_FMT "%04x:%04x:%04x:%04x:%04x:%04x:%04x:%04x"

#define INFINITY_LIFE_TIME      0xFFFFFFFFU

main()

{
      struct {
              struct nlmsghdr n;
              struct ifaddrmsg r;
//              char             buf[1024];                
      } req;

      struct rtattr *rta;
      struct sockaddr_in6 *sin6p;
      struct sockaddr_in *sinp;
      int status;
      char buf[16384];
      struct nlmsghdr *nlmp;
      struct ifaddrmsg *rtmp;
      struct rtattr *rtatp;
      int rtattrlen;
      struct in_addr *inp;
      struct in6_addr *in6p;
      struct ifa_cacheinfo *cache_info;

      int fd = socket(PF_NETLINK, SOCK_DGRAM, NETLINK_ROUTE);

      /* We use RTM_GETADDR to fetch the ip address from the kernel interface table *
         * So what we do here is pretty simple, we populate the msg structure (req)   *
         * the size of the message buffer is specified to netlink message header, and *
         * flags values are set as NLM_F_ROOT | NLM_F_REQUEST. The request flag must  *
         * be set for all messages requesting the data from kernel. The root flag is  *
         * used to notify the kernel to return the full tabel. Another flag (not used)*
         * is NLM_F_MATCH. This is used to get only speficed entried in the table.    *
         * At the time of writing this program this flag is not implemented in kernel */

      memset(&req, 0, sizeof(req));
      req.n.nlmsg_len = NLMSG_LENGTH(sizeof(struct ifaddrmsg));
      req.n.nlmsg_flags = NLM_F_REQUEST | NLM_F_ROOT;
      req.n.nlmsg_type = RTM_GETADDR;


      /* AF_INET6 is used to signify the kernel to fetch only ipv6 entires.         *
        * Replacing this with AF_INET will fetch ipv4 address table.                 */

      req.r.ifa_family = AF_INET6;

      /* Fill up all the attributes for the rtnetlink header. The code is pretty easy*
        * to understand. The lenght is very important. We use 16 to signify the ipv6  *
       * address. If the user chooses to use AF_INET (ipv4) the length has to be     *
        * RTA_LENGTH(4) */

      rta = (struct rtattr *)(((char *)&req) + NLMSG_ALIGN(req.n.nlmsg_len));
      rta->rta_len = RTA_LENGTH(16);

      /* Time to send and recv the message from kernel */

      status = send(fd, &req, req.n.nlmsg_len, 0);

      if (status < 0) {
              perror("send");
              return 1;
      }

      status = recv(fd, buf, sizeof(buf), 0);

      if (status < 0) {
              perror("recv");
              return 1;
      }

      if(status == 0){
              printf("EOF\n");
              return 1;
      }

      /* Typically the message is stored in buf, so we need to parse the message to *
        * get the required data for our display. */

      for(nlmp = (struct nlmsghdr *)buf; status > sizeof(*nlmp);){
              int len = nlmp->nlmsg_len;
              int req_len = len - sizeof(*nlmp);

              if (req_len<0 || len>status) {
                      printf("error\n");
                      return -1;
              }

              if (!NLMSG_OK(nlmp, status)) {
                      printf("NLMSG not OK\n");
                      return 1;
              }

              rtmp = (struct ifaddrmsg *)NLMSG_DATA(nlmp);
              rtatp = (struct rtattr *)IFA_RTA(rtmp);

              /* Start displaying the index of the interface */

              printf("Index Of Iface= %d\n",rtmp->ifa_index);

              rtattrlen = IFA_PAYLOAD(nlmp);

              for (; RTA_OK(rtatp, rtattrlen); rtatp = RTA_NEXT(rtatp, rtattrlen)) {
     
               /* Here we hit the fist chunk of the message. Time to validate the    *
                 * the type. For more info on the different types see man(7) rtnetlink*
                 * The table below is taken from man pages.                           *
                 * Attributes                                                         *
                 * rta_type        value type             description                 *
                 * -------------------------------------------------------------      *
                 * IFA_UNSPEC      -                      unspecified.                *
                 * IFA_ADDRESS     raw protocol address   interface address           *
                 * IFA_LOCAL       raw protocol address   local address               *
                 * IFA_LABEL       asciiz string          name of the interface       *
                 * IFA_BROADCAST   raw protocol address   broadcast address.          *
                 * IFA_ANYCAST     raw protocol address   anycast address             *
                 * IFA_CACHEINFO   struct ifa_cacheinfo   Address information.        */

                      if(rtatp->rta_type == IFA_CACHEINFO){
                              cache_info = (struct ifa_cacheinfo *)RTA_DATA(rtatp);
                              if (cache_info->ifa_valid == INFINITY_LIFE_TIME)
                                      printf("valid_lft forever\n");
                              else
                                      printf("valid_lft %usec\n", cache_info->ifa_valid);
  
                              if (cache_info->ifa_prefered == INFINITY_LIFE_TIME)
                                      printf(" preferred_lft forever\n");
                              else
                                      printf(" preferred_lft %usec\n",cache_info->ifa_prefered);
                      }

                      /* NOTE: All the commented code below can be used as it is for ipv4 table */

                      if(rtatp->rta_type == IFA_ADDRESS){
                              // inp = (struct in_addr *)RTA_DATA(rtatp);
                              in6p = (struct in6_addr *)RTA_DATA(rtatp);
                              printf("addr0: " NIP6_FMT "\n",NIP6(*in6p));
                              // printf("addr0: "NIPQUAD_FMT"\n",NIPQUAD(*inp));
                      }

                      if(rtatp->rta_type == IFA_LOCAL){
                              // inp = (struct in_addr *)RTA_DATA(rtatp);
                              in6p = (struct in6_addr *)RTA_DATA(rtatp);
                              printf("addr1: " NIP6_FMT "\n",NIP6(*in6p));
                              // printf("addr1: "NIPQUAD_FMT"\n",NIPQUAD(*inp));
                      }

                      if(rtatp->rta_type == IFA_BROADCAST){
                              // inp = (struct in_addr *)RTA_DATA(rtatp);
                              in6p = (struct in6_addr *)RTA_DATA(rtatp);
                              printf("bcataddr: " NIP6_FMT "\n",NIP6(*in6p));
                              // printf("Bcast addr: "NIPQUAD_FMT"\n",NIPQUAD(*inp));
                      }

                      if(rtatp->rta_type == IFA_ANYCAST){
                             //inp = (struct in_addr *)RTA_DATA(rtatp);
                             in6p = (struct in6_addr *)RTA_DATA(rtatp);
                             printf("anycastaddr: "NIP6_FMT"\n",NIP6(*in6p));
                            // printf("anycast addr: "NIPQUAD_FMT"\n",NIPQUAD(*inp));
                      }

              }
              status -= NLMSG_ALIGN(len);
              nlmp = (struct nlmsghdr*)((char*)nlmp + NLMSG_ALIGN(len));

      }

}

Collecting trace data from Linux kernel using klog

Many mechanisms exist to trace through the linux kernel code, both dynamically and statically. For example, for static tracing, one could use the markers or ftrace, and for dynamic tracing, there is kprobe, systemtap (which is built on top of kprobes). However, I was looking for a way to just dump some data from the kernel into a buffer and dump that data to the user at a later point in time. An example scenario being, while I am in the timer interrupt or in some other non-preemptible code section, I only wish to capture some timestamps, I cannot afford to do a printk from there. Also for instance, I want to instrument the scheduler code to capture timestamp information, I will be into trouble.. as, scheduler code being executed so very often, I will be bombarded with data and the depending on how much data I am collecting, the system could also become unusable.

I came across the klog kernel patch very recently. It was written by Tom Zanussi in 2005. Recently, Vaidyanathan Srinivasan made a few changes to klog, by adding the function ktrace, which makes it even more simpler to use it. Below, I describe how one could make use of this mechanism. Before we begin, note that klog is a static tracer. So, everytime you want to trace new code, the kernel will need to be recompiled.

Apply the klog patch to your kernel. This includes the changes made by Vaidy for ktrace. To trace through any code (ie, kernel routine), ktrace provides the following infrastructure:

1) Trace events (defined in include/linux/ktrace.h):

enum KTRACE_EVENT_ID {
KT_EVENT_FUNC_ENTER,
KT_EVENT_FUNC_EXIT,
KT_EVENT_INFO1,
KT_EVENT_INFO2,
KT_EVENT_INFO3,
KT_EVENT_INFO4,
KT_EVENT_ERROR,
};

2) Enumerator for the functions to be traced (include/linux/ktrace.h):

enum KTRACE_FUNC_ID {
KT_FUNC_tick_nohz_stop_sched_tick, /* 0 */
KT_FUNC_tick_nohz_restart_sched_tick, /* 1 */
};


3) Logging routines (lib/ktrace.c):

void ktrace_log2(unsigned char func, unsigned char event, uint64_t u1, uint64_t u2);
void ktrace_log4(unsigned char func, unsigned char event, uint32_t u1, uint32_t u2,
uint32_t u3, uint32_t u4);

So now, if you want to capture timestamps between the entry and exit of a routine x (assuming the routine executes in preempt disable mode), the following changes would be needed:

a) Add that function into the KTRACE_FUNC_ID,

enum KTRACE_FUNC_ID {
KT_FUNC_tick_nohz_stop_sched_tick, /* 0 */
KT_FUNC_tick_nohz_restart_sched_tick, /* 1 */
+ KT_FUNC_my_func_to_trace,
};

b) At the entry of the routine, capture the timestamp:

ktime_to_ns(start);

At the exit of the routine, make a call to ktrace_log2,

ktrace_log2(KT_FUNC_my_func_to_trace, KT_FUNC_EXIT,ktime_to_ns(now)-start, 0);

Now, whenever the routine is executed, the ktrace_log2 call will dump the information into the klog buffer. Compile and reboot into the modified kernel. Mount debugfs:

# mkdir /debug
# mount -t debugfs nodev /debug

Now run the klog.c program

# ./klog [-b subbuf-size -n n_subbufs]


The resultant trace data will be stored in ./cpu0..cpu[x] files. Remember that this data is in binary format and needs to be processed to convert into ascii. For that, a simple python program can be used. A sample python script could be as follows: (adopted from this script)

import os
import sys
import struct

# Globals
nr_cpus = 4

tracedata = []

cookedtrace = open("trace.txt", 'w')
for cpu in range(nr_cpus):
tracefile = open("cpu%d" % cpu)
while(1):
tracerecord = tracefile.read(24)
if not len(tracerecord):
break
tracerecordfields = struct.unpack("IBBBxQQ", tracerecord)
tracedata.append(tracerecordfields)
cookedtrace.write("U%-10d C%d F%X E%x %10d %10d\n" % tracerecordfields)
cookedtrace.close()

The above will generate trace.txt file, with the data in the different columsn. Further processing could be done based on the particular event type and function id, to capture more information. From the information captured, one could easily plot graphs usig gnuplot.

Understanding PER_CPU_LOCKED

per_cpu variables is one of the type of synchronization primitive available in the linux kernel.

As the name suggests, it it used by those data structures that need elements equal to the number of processor available.

This helps avoid contention and faster access due to cache coherency as the element of the per_cpu data structure accessed correponds "only" to the processor on which the kernel thread is running on.This obviously means preemption be disabled before accessing the per_cpu variables.

Now, in the realtime linux kernel (PREEMPT_RT patchset) the aim is to be as preemptible as possible so as to allow high priority tasks to preempt anyone and everyone. Hence the above assumption that preemption is disabled prior to accessing per_cpu variables breaks.

This happens because, usually spinlocks are used to disable preemption but in realtime linux, all these spinlocks are converted to rt-mutexes . rt-mutexes does not disable preemption and puts the process to sleep instead of spinning.

A task put to sleep, would not know on which processor it will wake up on. Hence, a task can be preempted while accessing a per_cpu var and scheduled on another processor. The value eventually read can be corrupted or illegal.

The solution is to declare variables as PER_CPU_LOCKED (DEFINE_PER_CPU_LOCKED, DECLARE_PER_CPU_LOCKED) instead of just PER_CPU DEFINE_PER_CPU, DECLARE_PER_CPU).

This new macro, associates a per-cpu sleeping lock (rt-mutex) with the per-cpu variable. So, even if a kernel thread accessing a per-cpu variable is scheduled on another cpu, this lock will ensure that the data read is correct.

The implication of this new macro is a performance hit, as the per-cpu variable being read on one processor could well be for some other processor.

This performance hit is alright as in "realtime" we care more about "latency" and "determinism" than "overall system performance".

Installing Amarok 2 Beta/RC on Fedora 9

Installing Amarok 2 Beta/RC is pretty straight forward except that the steps on the Amarok wiki are incomplete.

First you need to install cmake

# yum install cmake

After that, try compiling with

# cmake -DCMAKE_INSTALL_PREFIX=`kde4-config --prefix` -DCMAKE_BUILD_TYPE=debugfull

On a typical Fedora 9 setup, you'd instantly hit errors. Thats because multiple devel packages are missing.

# yum install -y kdelibs phonon* libgpod-devel prce

Another package that needs to be installed is libtags. Installing it via yum didnot solve the problem for me. So I had to download the code and install it from here
You will need libmtp. But the ones available in Fedora 9 won't help. Take ones from Fedora 10 repo from here and here

During make i hit a problem, amarok couldn't file libprce and libprceposix, even though they were installed.

# ln -s /usr/lib/libpcreposix.so.0 /usr/lib/libpcreposix
# ln -s /lib/libpcre.so.0 /usr/lib/libpcre.so

Phew!
After all of this, trying compiling amarok again.This time everything should go smooth.
Then do a make and make install.
The make step takes a lot of time.
You should be all set to use the latest and greatest Music Player i.e Amarok 2 RC1 (pun intended!)


The easy way to do this just install the rpm. Grab the beta rpm from here

# yum localinstall amarok-1.90-1.fc9.i386.rpm

The above will resolve all the necessary dependencies and install amarok 2 beta 1

Powered by ScribeFire.