Neeraj Gupta

TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms

2015-06-07T21:02:00.001-07:00


1.  Slow Start


   Old TCPs would start a connection with the sender injecting multiple
   segments into the network, up to the window size advertised by the
   receiver.  While this is OK when the two hosts are on the same LAN,
   if there are routers and slower links between the sender and the
   receiver, problems can arise.  Some intermediate router must queue
   the packets, and it's possible for that router to run out of space.
   [2] shows how this naive approach can reduce the throughput of a TCP
   connection drastically.



Stevens                     Standards Track                     [Page 1]

 
RFC 2001                          TCP                       January 1997


   The algorithm to avoid this is called slow start.  It operates by
   observing that the rate at which new packets should be injected into
   the network is the rate at which the acknowledgments are returned by
   the other end.

   Slow start adds another window to the sender's TCP:  the congestion
   window, called "cwnd".  When a new connection is established with a
   host on another network, the congestion window is initialized to one
   segment (i.e., the segment size announced by the other end, or the
   default, typically 536 or 512).  Each time an ACK is received, the
   congestion window is increased by one segment.  The sender can
   transmit up to the minimum of the congestion window and the
   advertised window.  The congestion window is flow control imposed by
   the sender, while the advertised window is flow control imposed by
   the receiver.  The former is based on the sender's assessment of
   perceived network congestion; the latter is related to the amount of
   available buffer space at the receiver for this connection.

   The sender starts by transmitting one segment and waiting for its
   ACK.  When that ACK is received, the congestion window is incremented
   from one to two, and two segments can be sent.  When each of those
   two segments is acknowledged, the congestion window is increased to
   four.  This provides an exponential growth, although it is not
   exactly exponential because the receiver may delay its ACKs,
   typically sending one ACK for every two segments that it receives.

   At some point the capacity of the internet can be reached, and an
   intermediate router will start discarding packets.  This tells the
   sender that its congestion window has gotten too large.

   Early implementations performed slow start only if the other end was
   on a different network.  Current implementations always perform slow
   start.


2.  Congestion Avoidance


   Congestion can occur when data arrives on a big pipe (a fast LAN) and
   gets sent out a smaller pipe (a slower WAN).  Congestion can also
   occur when multiple input streams arrive at a router whose output
   capacity is less than the sum of the inputs.  Congestion avoidance is
   a way to deal with lost packets.  It is described in [2].

   The assumption of the algorithm is that packet loss caused by damage
   is very small (much less than 1%), therefore the loss of a packet
   signals congestion somewhere in the network between the source and
   destination.  There are two indications of packet loss:  a timeout
   occurring and the receipt of duplicate ACKs.




Stevens                     Standards Track                     [Page 2]

 
RFC 2001                          TCP                       January 1997


   Congestion avoidance and slow start are independent algorithms with
   different objectives.  But when congestion occurs TCP must slow down
   its transmission rate of packets into the network, and then invoke
   slow start to get things going again.  In practice they are
   implemented together.

   Congestion avoidance and slow start require that two variables be
   maintained for each connection: a congestion window, cwnd, and a slow
   start threshold size, ssthresh.  The combined algorithm operates as
   follows:

   1.  Initialization for a given connection sets cwnd to one segment
       and ssthresh to 65535 bytes.

   2.  The TCP output routine never sends more than the minimum of cwnd
       and the receiver's advertised window.

   3.  When congestion occurs (indicated by a timeout or the reception
       of duplicate ACKs), one-half of the current window size (the
       minimum of cwnd and the receiver's advertised window, but at
       least two segments) is saved in ssthresh.  Additionally, if the
       congestion is indicated by a timeout, cwnd is set to one segment
       (i.e., slow start).

   4.  When new data is acknowledged by the other end, increase cwnd,
       but the way it increases depends on whether TCP is performing
       slow start or congestion avoidance.

      If cwnd is less than or equal to ssthresh, TCP is in slow start;
      otherwise TCP is performing congestion avoidance.  Slow start
      continues until TCP is halfway to where it was when congestion
      occurred (since it recorded half of the window size that caused
      the problem in step 2), and then congestion avoidance takes over.

      Slow start has cwnd begin at one segment, and be incremented by
      one segment every time an ACK is received.  As mentioned earlier,
      this opens the window exponentially:  send one segment, then two,
      then four, and so on.  Congestion avoidance dictates that cwnd be
      incremented by segsize*segsize/cwnd each time an ACK is received,
      where segsize is the segment size and cwnd is maintained in bytes.
      This is a linear growth of cwnd, compared to slow start's
      exponential growth.  The increase in cwnd should be at most one
      segment each round-trip time (regardless how many ACKs are
      received in that RTT), whereas slow start increments cwnd by the
      number of ACKs received in a round-trip time.






Stevens                     Standards Track                     [Page 3]

 
RFC 2001                          TCP                       January 1997


   Many implementations incorrectly add a small fraction of the segment
   size (typically the segment size divided by 8) during congestion
   avoidance.  This is wrong and should not be emulated in future
   releases.


3.  Fast Retransmit


   Modifications to the congestion avoidance algorithm were proposed in
   1990 [3].  Before describing the change, realize that TCP may
   generate an immediate acknowledgment (a duplicate ACK) when an out-
   of-order segment is received (Section 4.2.2.21 of [1], with a note
   that one reason for doing so was for the experimental fast-
   retransmit algorithm).  This duplicate ACK should not be delayed.
   The purpose of this duplicate ACK is to let the other end know that a
   segment was received out of order, and to tell it what sequence
   number is expected.

   Since TCP does not know whether a duplicate ACK is caused by a lost
   segment or just a reordering of segments, it waits for a small number
   of duplicate ACKs to be received.  It is assumed that if there is
   just a reordering of the segments, there will be only one or two
   duplicate ACKs before the reordered segment is processed, which will
   then generate a new ACK.  If three or more duplicate ACKs are
   received in a row, it is a strong indication that a segment has been
   lost.  TCP then performs a retransmission of what appears to be the
   missing segment, without waiting for a retransmission timer to
   expire.


4.  Fast Recovery


   After fast retransmit sends what appears to be the missing segment,
   congestion avoidance, but not slow start is performed.  This is the
   fast recovery algorithm.  It is an improvement that allows high
   throughput under moderate congestion, especially for large windows.

   The reason for not performing slow start in this case is that the
   receipt of the duplicate ACKs tells TCP more than just a packet has
   been lost.  Since the receiver can only generate the duplicate ACK
   when another segment is received, that segment has left the network
   and is in the receiver's buffer.  That is, there is still data
   flowing between the two ends, and TCP does not want to reduce the
   flow abruptly by going into slow start.

   The fast retransmit and fast recovery algorithms are usually
   implemented together as follows.






Stevens                     Standards Track                     [Page 4]

 
RFC 2001                          TCP                       January 1997


   1.  When the third duplicate ACK in a row is received, set ssthresh
       to one-half the current congestion window, cwnd, but no less
       than two segments.  Retransmit the missing segment.  Set cwnd to
       ssthresh plus 3 times the segment size.  This inflates the
       congestion window by the number of segments that have left the
       network and which the other end has cached (3).

   2.  Each time another duplicate ACK arrives, increment cwnd by the
       segment size.  This inflates the congestion window for the
       additional segment that has left the network.  Transmit a
       packet, if allowed by the new value of cwnd.

   3.  When the next ACK arrives that acknowledges new data, set cwnd
       to ssthresh (the value set in step 1).  This ACK should be the
       acknowledgment of the retransmission from step 1, one round-trip
       time after the retransmission.  Additionally, this ACK should
       acknowledge all the intermediate segments sent between the lost
       packet and the receipt of the first duplicate ACK.  This step is
       congestion avoidance, since TCP is down to one-half the rate it
       was at when the packet was lost.

   The fast retransmit algorithm first appeared in the 4.3BSD Tahoe
   release, and it was followed by slow start.  The fast recovery
   algorithm appeared in the 4.3BSD Reno release.


5.  Security Considerations


   Security considerations are not discussed in this memo.

TCP : Fast Retransmit

2015-05-26T06:47:00.000-07:00

Fast Retransmit is an enhancement to TCP which reduces the time a sender waits before retransmitting a lost segment.

A TCP sender uses a timer to recognize lost segments. If an acknowledgement is not received for a particular segment within a specified time (a function of the estimated Round-trip delay time), the sender will assume the segment was lost in the network, and will retransmit the segment.

Duplicate acknowledgement is the basis for the fast retransmit mechanism which works as follows: after receiving a packet (e.g. with sequence number 1), the receiver sends an acknowledgement by adding 1 to the sequence number (i.e., acknowledgement number 2) which means that the receiver receives the packet number 1 and it expects packet number 2 from the sender. Let's assume that three subsequent packets have been lost. In the meantime the receiver receives packet numbers 5 and 6. After receiving packet number 5, the receiver sends an acknowledgement, but still only for sequence number 2. When the receiver receives packet number 6, it sends yet another acknowledgement value of 2. Because the sender receives more than one acknowledgement with the same sequence number (2 in this example) this is called duplicate acknowledgement.

The fast retransmit enhancement works as follows: if a TCP sender receives a specified number of acknowledgements which is usually set to three duplicate acknowledgements with the same acknowledge number (that is, a total of four acknowledgements with the same acknowledgement number), the sender can be reasonably confident that the segment with the next higher sequence number was dropped, and will not arrive out of order. The sender will then retransmit the packet that was presumed dropped before waiting for its timeout.

LCM findFirstCommonAncestor

2015-05-25T21:16:00.000-07:00

TreeNode findFirstCommonAncestor(TreeNode root, int p, int q) { if (root == null) { return null; } if (root.value == p || root.value == q) { return root; } if (root.value > p && root.value > q ) { return findFirstCommonAncestor(root.left, p, q); } else if (root.value < p && root.value < q ) { return findFirstCommonAncestor(root.right, p, q); } else { return root; } }

Height of a Tree

2015-05-24T20:51:00.002-07:00

GeeksQuiz

Write a C Program to Find the Maximum Depth or Height of a Tree

Maximum depth or height of the below tree is 3.

Example Tree

Recursively calculate height of left and right subtrees of a node and assign height to the node as max of the heights of two children plus 1. See below pseudo code and program for details.
Algorithm:

 maxDepth()
1. If tree is empty then return 0
2. Else
     (a) Get the max depth of left subtree recursively  i.e., 
          call maxDepth( tree->left-subtree)
     (a) Get the max depth of right subtree recursively  i.e., 
          call maxDepth( tree->right-subtree)
     (c) Get the max of max depths of left and right 
          subtrees and add 1 to it for the current node.
         max_depth = max(max dept of left subtree,  
                             max depth of right subtree) 
                             + 1
     (d) Return max_depth

See the below diagram for more clarity about execution of the recursive function maxDepth() for above example tree.

            maxDepth('1') = max(maxDepth('2'), maxDepth('3')) + 1
                               = 2 + 1
                                  /    \
                                /         \
                              /             \
                            /                 \
                          /                     \
               maxDepth('1')                  maxDepth('3') = 1
= max(maxDepth('4'), maxDepth('5')) + 1
= 1 + 1   = 2         
                   /    \
                 /        \
               /            \
             /                \
           /                    \
 maxDepth('4') = 1     maxDepth('5') = 1

Implementation:

#include

#include

/* A binary tree node has data, pointer to left child 

   and a pointer to right child */

struct node 

{

    int data;

    struct node* left;

    struct node* right;

};

/* Compute the "maxDepth" of a tree -- the number of 

    nodes along the longest path from the root node 

    down to the farthest leaf node.*/

int maxDepth(struct node* node) 

{

   if (node==NULL) 

       return 0;

   else

   {

       /* compute the depth of each subtree */

       int lDepth = maxDepth(node->left);

       int rDepth = maxDepth(node->right);

       /* use the larger one */

       if (lDepth > rDepth) 

           return(lDepth+1);

       else return(rDepth+1);

   }

} 

/* Helper function that allocates a new node with the

   given data and NULL left and right pointers. */

struct node* newNode(int data) 

{

    struct node* node = (struct node*)

                                malloc(sizeof(struct node));

    node->data = data;

    node->left = NULL;

    node->right = NULL;

    return(node);

}

int main()

{

    struct node *root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

    root->left->left = newNode(4);

    root->left->right = newNode(5); 

    printf("Hight of tree is %d", maxDepth(root));

    getchar();

    return 0;

}

Time Complexity: O(n) (Please see our post Tree Traversal for details)

Interview Question at narus

2013-11-19T23:21:00.000-08:00

1. What is virtual memory and advantage and disadvantage of virtual memory
2. how compiler manage scoping of static variable
3. difference between macro and const variable
4. network buffers : linux
5. how watchdog run how do find that some CPU is locked
6. who restrict size of virtual memory
7. what is kernal memory size , can it be virtual
8. static gloabl and same static local variable in function is possible
9. what is volatile
10. fork what all it do

Linux kernal flow : v imp

2013-11-19T23:16:00.003-08:00

kernel_flow

By Linux Foundatio... - November 19, 2009 - 10:23am

networking

by Arnout Vandecappelle, Mind

http://www.linuxfoundation.org/collaborate/workgroups/networking/kernel_flow

This article describes the control flow (and the associated data buffering) of the Linux networking kernel. The picture on the left gives an overview of the flow. Open it in a separate window and use it as a reference for the explanation below.

This article is based on the 2.6.20 kernel. Please feel free to update for newer kernels.

Another article gives a similar description based on a 2.4.20 kernel. Unfortunately, that one is not on a Wiki so it can't be updated...

Preliminaries

Refer to Net:Network Overview for an overview of all aspects of the networking kernel: routing, neighbour discovery, NAPI, filtering, ...

The network data (including headers etc.) is managed through the sk_buff data structure. This minimizes copying overhead when going through the networking layers. A basic understanding of sk_buff is required to understand the networking kernel.

The kernel as a whole makes heavy use of virtual methods. These are recorded as function pointers in data structures. In the figure these are indicated with diamonds. This article never shows all possible implementations for these virtual methods, just the main ones.

This article only discusses TCP over IPv4 over Ethernet connections. Of course, many combinations of the different networking layers are possible, as well as tunnelling, bridging, etc.

Transmission path

Layer 5: Session layer (sockets and files)

There are three system calls that can send data over the network:

write (memory data to a file descriptor)
sendto (memory data to a socket)
sendmsg (a composite message to a socket)

All of these eventually end up in __sock_sendmsg(), which does security_sock_sendmsg() to check permissions and then forwards the message to the next layer using the socket's sendmsg virtual method.

Layer 4: Transport layer (TCP)

tcp_sendmsg: for each segment in the message

find an sk_buff with space available (use the one at the end if space left, otherwise allocate and append a new one)
copy data from user space to sk_buff data space (kernel space, probably DMA-able space) using skb_add_data().
- The buffer space is pre-allocated for each socket. If the buffer runs out of space, communication stalls: the data remains in user space until buffer space becomes available again (or the call returns with an error immediately if it was non-blocking).
- The size of allocated sk_buff space is equal to the MSS (Maximum Segment Size) + headroom (MSS may change during connection, and is modified by user options).
- Segmentation (or coalescing of individual writes) happens at this level. Whatever ends up in the same sk_buff will become a single TCP segment. Still, the segments can be fragmented further at IP level.
The TCP queue is activated; packets are sent with tcp_transmit_skb() (called multiple times if there are more active buffers).
tcp_transmit_skb() builds the TCP header (the allocation of the sk_buff has left space for it). It clones the skb in order to pass control to the network layer. The network layer is called through the queue_xmit virtual function of the socket's address family (inet_connection_sock->icsk_af_ops).

Layer 3: Network layer (IPv4)

ip_queue_xmit() does routing (if necessary), creates the IPv4 header
nf_hook() is called in several places to perform network filtering (firewall, NAT, ...). This hook may modify the datagram or discard it.
The routing decision results in a destination (dst_entry) object. This destination models the receiving IP address of the datagram. The dst_entry's output virtual method is called to perform actual output.
The sk_buff is passed on to ip_output() (or another output mechansim, e.g. in case of tunneling).
ip_output() does post-routing filtering, re-outputs it on a new destination if necessary due to netfiltering, fragments the datagram into packets if necessary, and finally sends it to the output device.
- Fragmentation tries to reuse existing fragment buffers, if possible. This happens when forwarding an already fragmented incoming IP packet. The fragment buffers are special sk_buff objects, pointing in the same data space (no copy required).
- If no fragment buffers are available, new sk_buff objects with new data space are allocated, and the data is copied.
- Note that TCP already makes sure the packets are smaller than MTU, so normally fragmentation is not required.
Device-specific output is again through a virtual method call, to output of the dst_entry's neighbour data structure. This usually is dev_queue_xmit. There is some optimisation for packets with a known destination (hh_cache).

Layer 2: Link layer (e.g. Ethernet)

The main function of the kernel at the link layer is scheduling the packets to be sent out. For this purpose, Linux uses the queueing discipline (struct Qdisc) abstraction. For detailed information, see Chapter 9 (Queueing Disciplines for Bandwidth Management) of the Linux Advanced Routing & Traffic Control HOWTO and Documentation//networking/multiqueue.txt.

dev_queue_xmit puts the sk_buff on the device queue using the qdisc->enqueue virtual method.

If necessary (when the device doesn't support scattered data) the data is linearised into the sk_buff. This requires copying.
Devices which don't have a Qdisc (e.g. loopback) go directly to dev_hard_start_xmit().
Several Qdisc scheduling policies exist. The basic and most used one is pfifo_fast, which has three priorities.

The device output queue is immediately triggered with qdisc_run(). It calls qdisc_restart(), which takes an skb from the queue using the qdisc->dequeue virtual method. Specific queueing disciplines may delay sending by not returning any skb, and setting up a qdisc_watchdog_timer() instead. When the timer expires, netif_schedule() is called to start transmission.

Eventually, the sk_buff is sent with dev_hard_start_xmit() and removed from the Qdisc. If sending fails, the skb is re-queued. netif_schedule() is called to schedule a retry.

netif_schedule() raises a software interrupt, which causes net_tx_action() to be called when the NET_TX_SOFTIRQ is ran by ksoftirqd. net_tx_action() calls qdisc_run() for each device with an active queue.

dev_hard_start_xmit() calls the hard_start_xmit virtual method for the net_device. But first, it calls dev_queue_xmit_nit(), which checks if a packet handler has been registered for the ETH_P_ALL protocol. This is used for tcpdump.

The device driver's hard_start_xmit function will generate one or more commands to the network device for scheduling transfer of the buffer. After a while, the network device replies that it's done. This triggers freeing of the sk_buff. If the sk_buff is freed from interrupt context, dev_kfree_skb_irq() is used. This delays the actual freeing until the next NET_TX_SOFTIRQ run, by putting the skb on the softnet_data completion_queue. This avoids doing frees from interrupt context.

Receive flow

Layer 2: Link layer (e.g. Ethernet)

The network device pre-allocates a number of sk_buffs for reception. How many, is configured per device. Usually, the addresses to the data space in these sk_buffs are configured directly as DMA area for the device. The device interrupt handler takes the sk_buff and performs reception handling on it. Before NAPI, this was done using netif_rx(). In NAPI, it is done in two phases.

From the interrupt handler, the device driver just calls netif_rx_schedule() and returns from interrupt. netif_rx_schedule() adds the device to sofnet_data's poll_list and raises the NET_RX_SOFTIRQ software interrupt.
ksoftirqd runs net_rx_action(), which calls the device's poll virtual method. The poll method does device-specific buffer management, calls netif_receive_skb() for each sk_buff, allocates new sk_buffs as required, and terminates with netif_rx_complete().

netif_receive_skb() finds out how to pass the sk_buff to upper layers.

netpoll_rx() is called, to support the Netpoll API
Call packet handlers for ETH_P_ALL protocol (for tcpdump)
Call handle_ing() for ingress queueing
Call handle_bridge() for bridging
Call handle_macvlan() for virtual LAN
Call the packet handler registered for the L3 protocol specified by the packet.

The packet handlers are called with the deliver_skb() function, which calls the protocol's func virtual method to handle the packet.

Layer 3: Network layer (IPv4, ARP)

ARP

ARP packets are handled with arp_rcv(). It processes the ARP information, stores it in the neighbour cache, and sends a reply if required. In the latter case, a new sk_buff (with new data space) is allocated for the reply.

IPv4

IPv4 packets are handled with ip_rcv(). It parses headers, checks for validity, sends an ICMP reply or error message if required. It also looks up the destination address using ip_route_input(). The destination's input virtual method is called with the sk_buff.

ip_mr_input() is called for multicast addresses. The packet may be forwarded using ip_mr_forward(), and it may be delivered locally using ip_local_delivery().
ip_forward() is called for packets with a different destination for which we have a route. It directly calls the neighbour's output virtual method.
ip_local_deliver() is called if this machine is the destination of the packet. Datagram fragments are collected here.

ip_local_deliver() delivers to any raw sockets for this connection first, using raw_local_deliver(). Then, it calls the L4 protocol handler for the protocol specified in the datagram. The L4 protocol is called even if a raw socket exists.

Throughout, xfrm4_policy_check calls are included to support IPSec.

Layer 4: Transport layer (TCP)

The net_protocol handler for TCP is tcp_v4_rcv(). Most of the code here deals with the protocol processing in TCP, for setting up connections, performing flow control, etc.

A received TCP packet may include an acknowledgement of a previously sent packet, which may trigger further sending of packets (tcp_data_snd_check()) or of acknowledgements (tcp_ack_snd_check()).

Passing the incoming packet to an upper layer is done in tcp_rcv_established() and tcp_data_queue(). These functions maintain the tcp connection's out_of_order_queue, and the socket's sk_receive_queue and sk_async_wait_queue. If a user process is already waiting for data to arrive, the data is immediately copied to user space using skb_copy_datagram_iovec(). Otherwise, the sk_buff is appended to one of the socket's queues and will be copied later.

Finally, the receive functions call the socket's sk_data_ready virtual method to signal that data is available. This wakes up waiting processes.

Layer 5: Session layer (sockets and files)

There are three system calls that can receive data from the network:

read (memory data from a file descriptor)
recvfrom (memory data from a socket)
recvmsg (a composite message from a socket)

All of these eventually end up in __sock_recvmsg(), which does security_sock_recvmsg() to check permissions and then requests the message to the next layer using the socket's recvmsg virtual method. This is often sock_common_recvmsg(), which calls the recvmsg virtual method of the socket's protocol.

tcp_recvmsg() either copies data from the socket's queue using skb_copy_datagram_iovec(), or waits for data to arrive using sk_wait_data(). The latter blocks and is woken up by the layer 4 processing.

Groups:

Networking in the Linux Kernel

2013-11-19T23:14:00.001-08:00

http://wiki.openwrt.org/doc/networking/praxis

Above we read merely about the theory of networking, about the basic ideas, about communication protocols and standards. Now, let us see, how all of this is being handled by the Linux Kernel 2.6:

Everything related is found under /net/. But drivers, for the network devices, are of course found /drivers/.

NOTE:

The Linux kernel is only one component of the operating system
1. it does require libraries itself (we at OpenWrt use the µCLibC, see →links.software.libraries) Section: 3 - C library functions
2. it is very modular and there are many modules
3. it does require applications to provide features to end users (these run in userspace)

The main interface between the kernel and userspace is the set of system calls. There are about system calls. Network related system calls include:

writes to socket

Network Data Flow through the Linux Kernel

Kernel Flow

Packet Handling

TX Transmission

Queue No.1: The application process does a write() on a socket and all the data is copied from the process space into the send socket buffer
Queue No.2: The data goes through the TCP/IP stack and the packets are put (Evaluation strategy#Call_by_reference) into the NIC's egress buffer (here works the packet scheduler)
Queue No.3: After a packet gets dequeued, the transmission procedure of the driver is called, and it is copied into the tx_ring, a ring buffer the driver shares with the NIC

RX Reception

Queue No.1: The hardware (NIC) puts all incoming network packets into the rx_ring, a ring buffer the driver shares with the NIC
Queue No.2: The IRQ handler of the driver takes the packet from the rx_ring, puts it (by (Evaluation strategy#Call_by_reference)) in the ingress buffer (aka backlog queue) and schedules a SoftIRQ (in former days, every incoming packet triggered an IRQ, since Kernel this is solved by polling instead)
Queue No.3: is the the receive socket buffer

Typical queue lengths

The socket buffers can be set by the application (set_sockopt())
- cat /proc/sys/net/core/rmem_default or cat /proc/sys/net/core/wmem_default
The default queuing discipline is a FIFO queue. Default length is 100 packets (ether_setup(): dev→queue_len, drivers/net/net_init.c)
The tx_ring and rx_ring are driver dependent (e.g. the e1000 driver set these lengths to 80 packets)
The backlog queue is 300 packets in size (/proc/sys/net/core/netdev_max_backlog). Once it is full, it waits for being totally empty to allow again an enqueue() (netif_rx(), net/core/dev.c).

/proc

/proc is the POSIX complient mount point for the Virtual Filesystem for the processes.

/proc/cpuinfo: processor information
/proc/meminfo: memory status
/proc/version: kernel version and build information
/proc/cmdline: kernel command line
/proc//environ: calling environment
/proc//cmdline: process command line

See Procfs or http://www.comptechdoc.org/os/linux/howlinuxworks/linux_hlproc.html or proc.txt

See → http://gettys.wordpress.com/2010/11/29/home-router-puzzle-piece-one-fun-with-your-switch/ for some "fun" with all the queues.

Transmitting

So you can install hardware capable of Ethernet (usually a network card or more precisely an Ethernet card) on two hosts, connect them with a standardized cable, like a Category 5 cable and communicate with one another over Ethernet as far as your software supports Ethernet Sooner or later the sausage will get to the Ethernet thingy of the network stack, this will prepare the data conforming to the Ethernet standard, then will deliver the frames to the network card drivers and this will make the hardware, the network card, transmit the data.

Receiving

The NIC on the other side will receive the signal, relay it to the Ethernet thingy of the network stack, this will create one huge data out of the Ethernet frames and relay it to the software.

When a packet is enqueued on an interface with dev queue xmit (in net/core/dev.c), the enqueue operation of the packet scheduler is triggered and qdisc wakeup is being called (innet/pkt_sched.h) to send the packet on that device.

A transmit queue is associated with each device. When a network packet is ready for transmission, the "networking code" will call the driver's hard_start_xmit()-function to let it know, a packet is waiting. The driver will then put that packet into the transmit queue of the hardware.

You find the sources for the whole TCP/IP protocol suite implementation

Zero Copy I: User-Mode Perspective

2013-11-18T03:15:00.003-08:00

Zero Copy I: User-Mode Perspective

From Issue #105
January 2003

Jan 01, 2003 By Dragan Stancevic

SysAdmin

Explaining what is zero-copy functionality for Linux, why it's useful and where it needs work.

By now almost everyone has heard of so-called zero-copy functionality under Linux, but I often run into people who don't have a full understanding of the subject. Because of this, I decided to write a few articles that dig into the matter a bit deeper, in the hope of unraveling this useful feature. In this article, we take a look at zero copy from a user-mode application point of view, so gory kernel-level details are omitted intentionally.

What Is Zero-Copy?

To better understand the solution to a problem, we first need to understand the problem itself. Let's look at what is involved in the simple procedure of a network server dæmon serving data stored in a file to a client over the network. Here's some sample code:

read(file, tmp_buf, len);
write(socket, tmp_buf, len);

Looks simple enough; you would think there is not much overhead with only those two system calls. In reality, this couldn't be further from the truth. Behind those two calls, the data has been copied at least four times, and almost as many user/kernel context switches have been performed. (Actually this process is much more complicated, but I wanted to keep it simple). To get a better idea of the process involved, take a look at Figure 1. The top side shows context switches, and the bottom side shows copy operations.

Figure 1. Copying in Two Sample System Calls

Step one: the read system call causes a context switch from user mode to kernel mode. The first copy is performed by the DMA engine, which reads file contents from the disk and stores them into a kernel address space buffer.
Step two: data is copied from the kernel buffer into the user buffer, and the read system call returns. The return from the call caused a context switch from kernel back to user mode. Now the data is stored in the user address space buffer, and it can begin its way down again.
Step three: the write system call causes a context switch from user mode to kernel mode. A third copy is performed to put the data into a kernel address space buffer again. This time, though, the data is put into a different buffer, a buffer that is associated with sockets specifically.
Step four: the write system call returns, creating our fourth context switch. Independently and asynchronously, a fourth copy happens as the DMA engine passes the data from the kernel buffer to the protocol engine. You are probably asking yourself, “What do you mean independently and asynchronously? Wasn't the data transmitted before the call returned?” Call return, in fact, doesn't guarantee transmission; it doesn't even guarantee the start of the transmission. It simply means the Ethernet driver had free descriptors in its queue and has accepted our data for transmission. There could be numerous packets queued before ours. Unless the driver/hardware implements priority rings or queues, data is transmitted on a first-in-first-out basis. (The forked DMA copy in Figure 1 illustrates the fact that the last copy can be delayed).
As you can see, a lot of data duplication is not really necessary to hold things up. Some of the duplication could be eliminated to decrease overhead and increase performance. As a driver developer, I work with hardware that has some pretty advanced features. Some hardware can bypass the main memory altogether and transmit data directly to another device. This feature eliminates a copy in the system memory and is a nice thing to have, but not all hardware supports it. There is also the issue of the data from the disk having to be repackaged for the network, which introduces some complications. To eliminate overhead, we could start by eliminating some of the copying between the kernel and user buffers.
One way to eliminate a copy is to skip calling read and instead call mmap. For example:

tmp_buf = mmap(file, len);
write(socket, tmp_buf, len);

To get a better idea of the process involved, take a look at Figure 2. Context switches remain the same.

Figure 2. Calling mmap

Step one: the mmap system call causes the file contents to be copied into a kernel buffer by the DMA engine. The buffer is shared then with the user process, without any copy being performed between the kernel and user memory spaces.
Step two: the write system call causes the kernel to copy the data from the original kernel buffers into the kernel buffers associated with sockets.
Step three: the third copy happens as the DMA engine passes the data from the kernel socket buffers to the protocol engine.
By using mmap instead of read, we've cut in half the amount of data the kernel has to copy. This yields reasonably good results when a lot of data is being transmitted. However, this improvement doesn't come without a price; there are hidden pitfalls when using the mmap+write method. You will fall into one of them when you memory map a file and then call write while another process truncates the same file. Your write system call will be interrupted by the bus error signal SIGBUS, because you performed a bad memory access. The default behavior for that signal is to kill the process and dump core—not the most desirable operation for a network server. There are two ways to get around this problem.
The first way is to install a signal handler for the SIGBUS signal, and then simply call return in the handler. By doing this the write system call returns with the number of bytes it wrote before it got interrupted and the errno set to success. Let me point out that this would be a bad solution, one that treats the symptoms and not the cause of the problem. Because SIGBUS signals that something has gone seriously wrong with the process, I would discourage using this as a solution.
The second solution involves file leasing (which is called “opportunistic locking” in Microsoft Windows) from the kernel. This is the correct way to fix this problem. By using leasing on the file descriptor, you take a lease with the kernel on a particular file. You then can request a read/write lease from the kernel. When another process tries to truncate the file you are transmitting, the kernel sends you a real-time signal, the RT_SIGNAL_LEASE signal. It tells you the kernel is breaking your write or read lease on that file. Your write call is interrupted before your program accesses an invalid address and gets killed by the SIGBUS signal. The return value of the write call is the number of bytes written before the interruption, and the errno will be set to success. Here is some sample code that shows how to get a lease from the kernel:

if(fcntl(fd, F_SETSIG, RT_SIGNAL_LEASE) == -1) {
    perror("kernel lease set signal");
    return -1;
}
/* l_type can be F_RDLCK F_WRLCK */
if(fcntl(fd, F_SETLEASE, l_type)){
    perror("kernel lease set type");
    return -1;
}

You should get your lease before mmaping the file, and break your lease after you are done. This is achieved by calli

Sendfile

In kernel version 2.1, the sendfile system call was introduced to simplify the transmission of data over the network and between two local files. Introduction of sendfile not only reduces data copying, it also reduces context switches. Use it like this:

sendfile(socket, file, len);

To get a better idea of the process involved, take a look at Figure 3.

Figure 3. Replacing Read and Write with Sendfile

Step one: the sendfile system call causes the file contents to be copied into a kernel buffer by the DMA engine. Then the data is copied by the kernel into the kernel buffer associated with sockets.
Step two: the third copy happens as the DMA engine passes the data from the kernel socket buffers to the protocol engine.
You are probably wondering what happens if another process truncates the file we are transmitting with the sendfile system call. If we don't register any signal handlers, the sendfile call simply returns with the number of bytes it transferred before it got interrupted, and the errno will be set to success.
If we get a lease from the kernel on the file before we call sendfile, however, the behavior and the return status are exactly the same. We also get the RT_SIGNAL_LEASE signal before the sendfile call returns.
So far, we have been able to avoid having the kernel make several copies, but we are still left with one copy. Can that be avoided too? Absolutely, with a little help from the hardware. To eliminate all the data duplication done by the kernel, we need a network interface that supports gather operations. This simply means that data awaiting transmission doesn't need to be in consecutive memory; it can be scattered through various memory locations. In kernel version 2.4, the socket buffer descriptor was modified to accommodate those requirements—what is known as zero copy under Linux. This approach not only reduces multiple context switches, it also eliminates data duplication done by the processor. For user-level applications nothing has changed, so the code still looks like this:

sendfile(socket, file, len);

To get a better idea of the process involved, take a look at Figure 4.

Figure 4. Hardware that supports gather can assemble data from multiple memory locations, eliminating another copy.

Step one: the sendfile system call causes the file contents to be copied into a kernel buffer by the DMA engine.
Step two: no data is copied into the socket buffer. Instead, only descriptors with information about the whereabouts and length of the data are appended to the socket buffer. The DMA engine passes data directly from the kernel buffer to the protocol engine, thus eliminating the remaining final copy.
Because data still is actually copied from the disk to the memory and from the memory to the wire, some might argue this is not a true zero copy. This is zero copy from the operating system standpoint, though, because the data is not duplicated between kernel buffers. When using zero copy, other performance benefits can be had besides copy avoidance, such as fewer context switches, less CPU data cache pollution and no CPU checksum calculations.
Now that we know what zero copy is, let's put theory into practice and write some code. You can download the full source code fromwww.xalien.org/articles/source/sfl-src.tgz. To unpack the source code, typetar -zxvf sfl-src.tgz at the prompt. To compile the code and create the random data file data.bin, run make.
Looking at the code starting with header files:

/* sfl.c sendfile example program
Dragan Stancevic <
header name                 function / variable
-------------------------------------------------*/
#include           /* printf, perror */
#include           /* open */
#include          /* close */
#include           /* errno */
#include          /* memset */
#include      /* socket */
#include      /* sockaddr_in */
#include    /* sendfile */
#include       /* inet_addr */
#define BUFF_SIZE (10*1024) /* size of the tmp
                               buffer */

Besides the regular and required for basic socket operation, we need a prototype definition of the sendfile system call. This can be found in the server flag:

/* are we sending or receiving */
if(argv[1][0] == 's') is_server++;
/* open descriptors */
sd = socket(PF_INET, SOCK_STREAM, 0);
if(is_server) fd = open("data.bin", O_RDONLY);

The same program can act as either a server/sender or a client/receiver. We have to check one of the command-prompt parameters, and then set the flag is_server to run in sender mode. We also open a stream socket of the INET protocol family. As part of running in server mode we need some type of data to transmit to a client, so we open our data file. We are using the system call sendfile to transmit data, so we don't have to read the actual contents of the file and store it in our program memory buffer. Here's the server address:

/* clear the memory */
memset(&sa, 0, sizeof(struct sockaddr_in));
/* initialize structure */
sa.sin_family = PF_INET;
sa.sin_port = htons(1033);
sa.sin_addr.s_addr = inet_addr(argv[2]);

We clear the server address structure and assign the protocol family, port and IP address of the server. The address of the server is passed as a command-line parameter. The port number is hard coded to unassigned port 1033. This port number was chosen because it is above the port range requiring root access to the system.
Here is the server execution branch:

if(is_server){
    int client; /* new client socket */
    printf("Server binding to [%s]\n", argv[2]);
    if(bind(sd, (struct sockaddr *)&sa,
                      sizeof(sa)) < 0){
        perror("bind");
        exit(errno);
    }

As a server, we need to assign an address to our socket descriptor. This is achieved by the system call bind, which assigns the socket descriptor (sd) a server address (sa):

if(listen(sd,1) < 0){
    perror("listen");
    exit(errno);
}

Because we are using a stream socket, we have to advertise our willingness to accept incoming connections and set the connection queue size. I've set the backlog queue to 1, but it is common to set the backlog a bit higher for established connections waiting to be accepted. In older versions of the kernel, the backlog queue was used to prevent syn flood attacks. Because the system call listen changed to set parameters for only established connections, the backlog queue feature has been deprecated for this call. The kernel parameter tcp_max_syn_backlog has taken over the role of protecting the system from syn flood attacks:

if((client = accept(sd, NULL, NULL)) < 0){
    perror("accept");
    exit(errno);
}

The system call accept creates a new connected socket from the first connection request on the pending connections queue. The return value from the call is a descriptor for a newly created connection; the socket is now ready for read, write or poll/select system calls:

if((cnt = sendfile(client,fd,&off,
                          BUFF_SIZE)) < 0){
    perror("sendfile");
    exit(errno);
}
printf("Server sent %d bytes.\n", cnt);
close(client);

A connection is established on the client socket descriptor, so we can start transmitting data to the remote system. We do this by calling the sendfile system call, which is prototyped under Linux in the following manner:

extern ssize_t
sendfile (int __out_fd, int __in_fd, off_t *offset,
          size_t __count) __THROW;

The first two parameters are file descriptors. The third parameter points to an offset from which sendfile should start sending data. The fourth parameter is the number of bytes we want to transmit. In order for the sendfile transmit to use zero-copy functionality, you need memory gather operation support from your networking card. You also need checksum capabilities for protocols that implement checksums, such as TCP or UDP. If your NIC is outdated and doesn't support those features, you still can use sendfile to transmit files. The difference is the kernel will merge the buffers before transmitting them.ng fcntl F_SETLEASE with the lease type of F_UNLCK.

Portability Issues

One of the problems with the sendfile system call, in general, is the lack of a standard implementation, as there is for the open system call. Sendfile implementations in Linux, Solaris or HP-UX are quite different. This poses a problem for developers who wish to use zero copy in their network data transmission code.
One of the implementation differences is Linux provides a sendfile that defines an interface for transmitting data between two file descriptors (file-to-file) and (file-to-socket). HP-UX and Solaris, on the other hand, can be used only for file-to-socket submissions.
The second difference is Linux doesn't implement vectored transfers. Solaris sendfile and HP-UX sendfile have extra parameters that eliminate overhead associated with prepending headers to the data being transmitted.

Looking Ahead

The implementation of zero copy under Linux is far from finished and is likely to change in the near future. More functionality should be added. For example, the sendfile call doesn't support vectored transfers, and servers such as Samba and Apache have to use multiple sendfile calls with the TCP_CORK flag set. This flag tells the system more data is coming through in the next sendfile calls. TCP_CORK also is incompatible with TCP_NODELAY and is used when we want to prepend or append headers to the data. This is a perfect example of where a vectored call would eliminate the need for multiple sendfile calls and delays mandated by the current implementation.
One rather unpleasant limitation in the current sendfile is it cannot be used when transferring files greater than 2GB. Files of such size are not all that uncommon today, and it's rather disappointing having to duplicate all that data on its way out. Because both sendfile and mmap methods are unusable in this case, a sendfile64 would be really handy in a future kernel version.

Conclusion

Despite some drawbacks, zero-copy sendfile is a useful feature, and I hope you have found this article informative enough to start using it in your programs. If you have a more in-depth interest in the subject, keep an eye out for my second article, titled “Zero Copy II: Kernel Perspective”, where I will dig a bit more into the kernel internals of zero copy.

What are high memory and low memory on Linux?

2013-11-15T03:00:00.000-08:00

On a 32-bit architecture, the address space range for addressing RAM is:

0x00000000 - 0xffffffff

or 4'294'967'295 (4 GB).

The linux kernel splits that up 3/1 (could also be 2/2, or 1/3) into user space (high memory) and kernel space (low memory) respectively.

The user space range:

0x00000000 - 0xbfffffff

Every newly spawned user process gets an address (range) inside this area. User processes are generally untrusted and therefore are forbidden to access the kernel space. Further, they are considered non-urgent, as a general rule, the kernel tries to defer the allocation of memory to those processes.

The kernel space range:

0xc0000000 - 0xffffffff

A kernel processes gets its address (range) here. The kernel can directly access this 1 GB of addresses (well, not the full 1 GB, there are 128 MB reserved for high memory access).

Processes spawned in kernel space are trusted, urgent and assumed error-free, the memory request gets processed instantaneously.

Every kernel process can also access the user space range if it wishes to. And to achieve this, the kernel maps an address from the user space (the high memory) to its kernel space (the low memory), the 128 MB mentioned above are especially reserved for this.

What is difference between User space and Kernel space

2013-11-15T02:54:00.001-08:00

Is Kernel space used when Kernel is executing on the behalf of the user program i.e. System Call? Or is it the address space for all the Kernel threads (for example scheduler)?

Yes and yes.

Before we go any further, we should state this about memory.

Memory get's divided into two distinct areas:

The user space, which is a set of locations where normal user processes run (i.e everything other than the kernel). The role of the kernel is to manage applications running in this space from messing with each other, and the machine, and
The kernel space, which is the location where the code of the kernel is stored, and executes under.

Processes running under the user space have access only to a limited part of memory, whereas the kernel has access to all of the memory. Processes running in user space also don't have access to the kernel space. User space processes can only access a small part of the kernel via an interface exposed by the kernel - the system calls. If an process performs a system call, a software interrupt is sent to the kernel, which then dispatches the appropriate interrupt handler and continues its work after the handler has finished.

Kernel space code has the property to run in "kernel mode", which (in your typical desktop -x86- computer) is what you call code that executes under ring 0. Typically in x86 architecture, there are 4 rings of protection. Ring 0 (kernel mode), Ring 1 (may be used by virtual machine hypervisors or drivers), Ring 2 (may be used by drivers, I am not so sure about that though) and Ring 3. Ring 3 is what typical applications run under. It is the least privileged ring, and applications running on it have access to a subset of the processor's instructions. Ring 0 (kernel space) is the most privileged ring, and has access to all of the machine's instructions. For example to this, a "plain" application (like a browser) can not use x86 assembly instructions lgdt to load the global descriptor table or hlt to halt a processor.

If it is the first one, than does it mean that normal user program cannot have more than 3GB of memory (if the division is 3GB + 1GB)? Also, in that case how can kernel use High Memory, because to what virtual memory address will the pages from high memory be mapped to, as 1GB of kernel space will be logically mapped?

For an answer to this, please refer to the excellent answer by wag here

NAT DSlite 6rd NAT64

2013-11-14T22:41:00.002-08:00

NAT

Network components

1. DS lite

DS-Lite enables service providers to natively allocate IPv6 addresses to new customers while continuing to support IPv4 customers. Main functional components involved in DS-Lite are B4 (Basic Bridging BroadBand) and AFTR (Address Family Translation Router) as shown in figure below:

Following sequence describes the connection establishment process using DS Lite:

Host with private IPv4 address initiates a connection to a resource on the public internet
Traffic is sent to B4, which is the default gateway
B4, using its service provider network facing IPv6 addresses establishes the tunnel with AFTR. Address of the AFTR can be pre-configured or can be discovered using DHCPv6
B4 encapsulates the IPv4 packets in IPv6 transport and sends across to AFTR
AFTR terminates the tunnel and de-capsulate the IPv4 packet
AFTR device performs IPv4-IPv4 NAT before sending traffic to the destination IPv4 network

There are many benefits that DS Lite provides:

A lightweight solution to allow IPv4 connectivity over IPv6 network
Avoids the need of multiple levels of NAT as in case of LSN
Allows service providers to move their core and access networks to IPv6 thus enabling them to benefit from IPv6 advantages
Allows coexistence of IPv4 and IPv6
Helps resolve IPv4 address scarcity issue
Allows incremental migration to native IPv6 environmen

But as always is the case, benefits don’t come without its own set of challenges:

DS Lite does not provide IPv6 and IPv4 hosts to talk to each other
Increases the size of traffic due to tunnel headers – requires MTU management to avoid fragmentation
Need to manage and maintain bindings between customer addresses and public addresses used for translation in the AFTR device
Brings in additional challenges for DPI in service provider network

2. 6rd
6rd is a mechanism to facilitate IPv6 rapid deployment across IPv4 infrastructures of Internet service providers (ISPs).

6rd is just opposite of DS lite (just replace v4 to v6)

It is derived from 6to4, a preexisting mechanism to transfer IPv6 packets over the IPv4 network, with the significant change that it operates entirely within the end-user's ISP's network, thus avoiding the major architectural problems inherent in the original design of 6to4. The name 6rd is a reference to both the rapid deployments of IPv6 it makes possible and, informally, the initials (RD) of its inventor, Rémi Després. A description of 6rd principles and of how they were first used by Free is published in RFC 5569.^[1]

Service Providers to provision IPv6 addresses to end customers without upgrading their core infrastructure to IPv6. 6rd enables IPv6 hosts separated by IPv4 networks to communicate with each other by establishing an IPv4 tunnel. The tunnel origination point on the sender’s side of the tunnel encapsulates the IPv6 traffic within IPv4 packets, and sends them over IPv4 to the device at the remote end of the tunnel. The device on the other end of the tunnel decapsulates the packets and sends them over the IPv6 network to their destination.

Though 6rd helps ISPs to provision IPv6 connectivity to end users but it does not allow IPv6 clients to talk with IPv4 servers. For that to work solutions like NAT64 / SLB64 are required.

3. NAT64

This brings in the challenge of ensuring that new IPv6 enabled devices are able to access any content – hosted on IPv4 or IPv6. NAT64 is technology that provides the bridge between IPv6 and IPv4 by doing the protocol transformation that the other side understands.

NAT64 does the translation from IPv6 to IPv4 based on a pre-assigned /96 prefix that is carried in the destination IPv6 address of packets. Last 32 bits of the IPv6 address carry the
IPv4 address of the destination IPv4 host. As the traffic passes through the NAT64 device, it looks for the prefix match – if the match is found, the device knows that the destination is IPv4 host and needs translation. Unlike the good old NAT devices, NAT64 devices need to perform protocol transformation – creating an IPv4 header based on the information in the IPv6 header. There are additional requirements to make sure that two disparate networks can talk to each other like ICMP translation along with translation of traditional applications that embed Layer 3/4 information in the packets (e.g. FTP, SIP etc).

Now the question is – how does the connection initiating IPv6 host knows the destination address? This gap is filled by DNS64 device. Whenever DNS64 device gets a query (AAAA) to resolve a name – it first tries to fetch the IPv6 address. If the address is found, it is returned to the host but if there is no IPv6 address – DNS64 device gets the IPv4 address prepends it with the preconfigured 96 bit prefix and returns to the host. Following diagram shows the sequence of events when an IPv6 host tries to connect with an IPv4 server.

In early stages of IPv6 transition content providers are primarily providing access to web content hosted on IPv4 servers. In such scenarios SLB64 offer advantages over pure NAT64 technology. SLB64 is Server Load Balancing by exposing IPv6 connection points for IPv4 servers – so SLB64 devices not only provide translation but also provide other benefits that come along with advanced ADCs like NetScaler.

There are many detractors of NAT yet there is no denying that NAT has been in use for years and is not going away anywhere soon. For IPv6 transition it is emerging as a very strong enabling technology.

2013-11-11T21:45:00.001-08:00

Barracuda Networks Interview

1. kernal space and user spce commmunication

2. pagging, virtual memory

3. 32bit and 64bit machine ,what is sizeof (int) in 64 bit machine

Mutex vs. Semaphores

2013-07-22T06:45:00.003-07:00

Mutex vs. Semaphores – Part 1: Semaphores

It never ceases to amaze me how often I see postings in newsgroups, etc. asking the difference between a semaphore and a mutex. Probably what baffles me more is that over 90% of the time the responses given are either incorrect or missing the key differences. The most often quoted response is that of the “The Toilet Example (c) Copyright 2005, Niclas Winquist” . This summarises the differences as:

A mutex is really a semaphore with value 1

No, no and no again. Unfortunately this kind of talk leads to all sorts of confusion and misunderstanding (not to mention companies like Wind River Systems redefining a mutex as a “Mutual-Exclusion Semaphore” – now where is that wall to bang my head against?).
Firstly we need to clarify some terms and this is best done by revisiting the roots of the semaphore. Back in 1965, Edsger Dijkstra, a Dutch computer scientist, introduced the concept of a binary semaphore into modern programming to address possible race conditions in concurrent programs. His very simple idea was to use a pair of function calls to the operating system to indicate entering and leaving a critical region. This was achieved through the acquisition and release of an operating system resource called a semaphore. In his original work, Dijkstra used the notation of P & V, from the Dutch words Prolagen (P), a neologism coming from To try and lower, and Verhogen (V) To raise, To increase.

With this model the first task arriving at the P(S) [where S is the semaphore] call gains access to the critical region. If a context switch happens while that task is in the critical region, and another task also calls on P(S), then that second task (and any subsequent tasks) will be blocked from entering the critical region by being put in a waiting state by the operating system. At a later point the first task is rescheduled and calls V(S) to indicate it has left the critical region. The second task will now be allowed access to the critical region.
A variant of Dijkstra’s semaphore was put forward by another Dutchman, Dr. Carel S. Scholten. In his proposal the semaphore can have an initial value (or count) greater than one. This enables building programs where more than one resource is being managed in a given critical region. For example, a counting semaphore could be used to manage the parking spaces in a robotic parking system. The initial count would be set to the initial free parking places. Each time a place is used the count is decremented. If the count reaches zero then the next task trying to acquire the semaphore would be blocked (i.e. it must wait until a parking space is available). Upon releasing the semaphore (A car leaving the parking system) the count is incremented by one.
Scholten’s semaphore is referred to as the General or Counting Semaphore, Dijkstra’s being known as theBinary Semaphore.
Pretty much all modern Real-Time Operating Systems (RTOS) support the semaphore. For the majority, the actual implementation is based around the counting semaphore concept. Programmers using these RTOSs may use an initial count of 1 (one) to approximate to the binary semaphore. One of the most notable exceptions is probably the leading commercial RTOS VxWorks from Wind River Systems. This has two separate APIs for semaphore creation, one for the Binary semaphore (semBCreate) and another for the Counting semaphore (semCCreate).
Hopefully we now have a clear understanding of the difference between the binary semaphore and the counting semaphore. Before moving onto the mutex we need to understand the inherent dangers associated with using the semaphore. These include:

Accidental release
Recursive deadlock
Task-Death deadlock
Priority inversion
Semaphore as a signal

All these problems occur at run-time and can be very difficult to reproduce; making technical support very difficult.

Accidental release

This problem arises mainly due to a bug fix, product enhancement or cut-and-paste mistake. In this case, through a simple programming mistake, a semaphore isn’t correctly acquired but is then released.

When the counting semaphore is being used as a binary semaphore (initial count of 1 – the most common case) this then allows two tasks into the critical region. Each time the buggy code is executed the count is increment and yet another task can enter. This is an inherent weakness of using the counting semaphore as a binary semaphore.

Deadlock

Deadlock occurs when tasks are blocked waiting on some condition that can never become true, e.g. waiting to acquire a semaphore that never becomes free. There are three possible deadlock situations associated with the semaphore:

Recursive Deadlock
Deadlock through Death
Cyclic Deadlock (Deadly Embrace)

Here we shall address the first two, but shall return to the cyclic deadlock in a later posting.

Recursive Deadlock

Recursive deadlock can occur if a task tries to lock a semaphore it has already locked. This can typically occur in libraries or recursive functions; for example, the simple locking of malloc being called twice within the framework of a library. An example of this appeared in the MySQL database bug reporting system: Bug #24745 InnoDB semaphore wait timeout/crash – deadlock waiting for itself

Deadlock through Task Death

What if a task that is holding a semaphore dies or is terminated? If you can’t detect this condition then all tasks waiting (or may wait in the future) will never acquire the semaphore and deadlock. To partially address this, it is common for the function call that acquires the semaphore to specify an optional timeout value.

Priority Inversion

The majority of RTOSs use a priority-driven pre-emptive scheduling scheme. In this scheme each task has its own assigned priority. The pre-emptive scheme ensures that a higher priority task will force a lower priority task to release the processor so it can run. This is a core concept to building real-time systems using an RTOS. Priority inversion is the case where a high priority task becomes blocked for an indefinite period by a low priority task. As an example:

An embedded system contains an “information bus”
Sequential access to the bus is protected with a semaphore.
A bus management task runs frequently with a high priority to move certain kinds of data in and out of the information bus.
A meteorological data gathering task runs as an infrequent, low priority task, using the information bus to publish its data. When publishing its data, it acquires the semaphore, writes to the bus, and release the semaphore.
The system also contains a communications task which runs with medium priority.
Very infrequently it is possible for an interrupt to occur that causes the (medium priority) communications task to be sch
eduled while the (high priority) information bus task is blocked waiting for the (low priority) meteorological data task.
In this case, the long-running communications task, having higher priority than the meteorological task, prevents it from running, consequently preventing the blocked information bus task from running.
After some time has passed, a watchdog timer goes off, notices that the data bus task has not been executed for some time, concludes that something has gone drastically wrong, and initiate a total system reset.

This well reported event actual sequence of events happened on NASA JPL’s Mars Pathfinder spacecraft.

Semaphore as a Signal

Unfortunately, the term synchronization is often misused in the context of mutual exclusion. Synchronization is, by definition “To occur at the same time; be simultaneous”. Synchronization between tasks is where, typically, one task waits to be notified by another task before it can continue execution (unilateral rendezvous). A variant of this is either task may wait, called the bidirectional rendezvous. This is quite different to mutual exclusion, which is a protection mechanism. However, this misuse has arisen as the counting semaphore can be used for unidirectional synchronization. For this to work, the semaphore is created with a count of 0 (zero).

Note that the P and V calls are not used as a pair in the same task. In the example, assuming Task1 calls the P(S) it will block. When Task 2 later calls the V(S) then the unilateral synchronization takes place and both task are ready to run (with the higher priority task actually running). Unfortunately “misusing” the semaphore as synchronization primitive can be problematic in that it makes debugging harder and increase the potential to miss “accidental release” type problems, as an V(S) on its own (i.e. not paired with aP(S)) is now considered legal code.
In the next posting I shall look at how the mutex address most of the weaknesses of the semaphore.

Mutex vs. Semaphores – Part 2: The Mutex

In Part 1 of this series we looked at the history of the binary and counting semaphore, and then went on to discuss some of the associated problem areas. In this posting I aim to show how a different RTOS construct, the mutex, may overcome some, if not all, of these weaknesses.
To address the problems associated with semaphore, a new concept was developed during the late 1980’s. I have struggled to find it’s first clear definition, but the major use of the term mutex (another neologism based around MUTual EXclusion) appears to have been driven through the development of the common programming specification for UNIX based systems. In 1990 this was formalised by the IEEE as standard IEEE Std 1003.1 commonly known as POSIX.
The mutex is similar to the principles of the binary semaphore with one significant difference: the principle of ownership. Ownership is the simple concept that when a task locks (acquires) a mutex only it can unlock (release) it. If a task tries to unlock a mutex it hasn’t locked (thus doesn’t own) then an error condition is encountered and, most importantly, the mutex is not unlocked. If the mutual exclusion object doesn’t have ownership then, irrelevant of what it is called, it is not a mutex.
The concept of ownership enables mutex implementations to address the problems discussed in part 1:

Accidental release
Recursive deadlock
Task-Death deadlock
Priority inversion
Semaphore as a signal

Accidental Release
As already stated, ownership stops accidental release of a mutex as a check is made on the release and an error is raised if current task is not owner.
Recursive Deadlock
Due to ownership, a mutex can support relocking of the same mutex by the owning task as long as it is released the same number of times.
Priority Inversion
With ownership this problem can be addressed using one of the following priority inheritance protocols:

[Basic] Priority Inheritance Protocol
Priority Ceiling Protocol

The Basic Priority Inheritance Protocol enables a low-priority task to inherit a higher-priorities task’s priority if this higher-priority task becomes blocked waiting on a mutex currently owned by the low-priority task. The low priority task can now run and unlock the mutex – at this point it is returned back to its original priority.
The details of the Priority Inheritance Protocol and Priority Ceiling Protocol (a slight variant) will be covered in part 3 of this series.
Death Detection
If a task terminates for any reason, the RTOS can detect if that task current owns a mutex and signal waiting tasks of this condition. In terms of what happens to the waiting tasks, there are various models, but two doiminate:

All tasks readied with error condition;
Only one task readied; this task is responsible for ensuring integrity of critical region.

When all tasks are readied, these tasks must then assume critical region is in an undefined state. In this model no task currently has ownership of the mutex. The mutex is in an undefined state (and cannot be locked) and must be reinitialized.
When only one task is readied, ownership of the mutex is passed from the terminated task to the readied task. This task is now responsible for ensuring integrity of critical region, and can unlock the mutex as normal.
Mutual Exclusion / Synchronisation
Due to ownership a mutex cannot be used for synchronization due to lock/unlock pairing. This makes the code cleaner by not confusing the issues of mutual exclusion with synchronization.
Caveat
A specific Operating Systems mutex implementation may or may not support the following:

Recursion
Priority Inheritance
Death Detection

Review of some APIs
It should be noted that many Real-Time Operating Systems (or more correctly Real-Time Kernels) do not support the concept of the mutex, only supporting the Counting Semaphore (e.g. MicroC/OS-II). [ CORRECTION: The later versions of uC/OS-II do support the mutex, only the original version did not].
In this section we shall briefly examine three different implementations. I have chosen these as they represent the broad spectum of APIs offered (Footnote 1):

VxWorks Version 5.4
POSIX Threads (pThreads) – IEEE Std 1003.1, 2004 Edition
Microsoft Windows Win32 – Not .NET

VxWorks from Wind River Systems is among the leading commercial Real-Time Operating System used in embedded systems today. POSIX Threads is a widely supported standard, but has become more widely used due to the growth of the use of Embedded Linux. Finally Microsoft Window’s common programming API, Win32 is examined. Windows CE, targeted at embedded development, supports this API.
However, before addressing the APIs in detail we need to introduce the concept of a Release Order Policy. In Dijkstra’s original work the concept of task priorities were not part of the problem domain. Therefore it was assumed that if more than one task was waiting on a held semaphore, when released the next task to acquire the semaphore would be chosen on a First-Come-First-Server (First-In-First-Out; FIFO) policy. However once tasks have priorities, the policy may be:

FIFO – waiting tasks ordered by arrival time
Priority – waiting tasks ordered by priority
Undefined - implementation doesn’t specify

VxWorks v5.4
VxWorks supports the Binary Semaphore, the Counting Semaphore and the Mutex (called the Mutual-Exclusion Semaphore in VxWorks terminology). They all support a common API for acquiring (semTake) and releasing (semGive) the particular semaphore. For all semaphore types, waiting tasks can be queued by priority or FIFO and can have a timeout specified.
The Binary Semaphore has, as expected, no support for recursion or inheritance and the taker and giver do not have to be same task. Some additional points of interest are that there is no effect of releasing the semaphore again; It can be used as a signal (thus can be created empty); and supports the idea of a broadcast release (wake up all waiting tasks rather than just the first). The Counting Semaphore, as expected, is the same as the Binary Semaphore with ability to define an initial count.
The Mutual-Exclusion Semaphore is the VxWorks mutex. Only the owning task may successfully call semGive. The VxWorks mutex also has the ability to support both priority inheritance (basic priority inheritance protocol) and deletion safety.
POSIX
POSIX is an acronym for Portable Operating System Interface (the X has no meaning). The current POSIX standard is formally defined by IEEE Std 1003.1, 2004 Edition. The mutex is part of the core POSIX Threads (pThreads) specification (historically referred to as IEEE Std 1003.1c-1995).
POSIX also supports both semaphores and priority-inheritance mutexes as part of what are called Feature Groups. Support for these Feature Groups is optional, but when an implementation claims that a feature is provided, all of its constituent parts must be provided
and must comply with this specification. There are two main Feature Groups of interest, the Realtime Group and Realtime Threads Groups.
The semaphore is not part of the core standard but is supported as part of the Realtime Feature Group. The Realtime Semaphore is an implementation of the Counting semaphore.
The default POSIX mutex is non-recursive , has no priority inheritance support or death detection.
However, the Pthreads standard allows for non-portable extensions (as long as they are tagged with “-np”). A high proportion of programmers using POSIX threads are programming for Linux. Linux supports four different mutex types through non-portable extensions:

Fast mutex – non-recursive and will deadlock [default]
Error checking mutex – non-recursive but will report error
Recursive mutex – as the name implies
Adaptive mutex - extra fast for mutli-processor systems

These are extreamly well covered by Chris Simmonds in his posting Mutex mutandis: understanding mutex types and attributes.
Finally the Realtime Threads Feature Group adds mutex support for both priority inheritance and priority ceiling protocols.
Win32 API
Microsoft Window’s common API is referred to as Win32. This API supports three different primitives:

Semaphore – The counting semaphore
Critical Section - Mutex between threads in the same process; Recursive, no timeout, queuing order undefined
Mutex – As per critical sections, but can be used by threads in different processes; Recursive, timeout, queuing order undefined

The XP/Win32 mutex API does not support priority inheritance in application code, however the WinCE/Win32 API does!
Win32 mutexes do have built-in death detection; if a thread terminates when holding a mutex, then that mutex is said to be abandoned. The mutex is released (with WAIT_ABANDONED error code) and a waiting thread will take ownership. Note that Critical sections do not have any form of death detection.
Critical Sections have no timeout ability, whereas mutexes do. However Critical Sections support a separate function call TryEnterCriticalSection. A major weakness of the Win32 API is that the queuing model is undefined (i.e. neither Priority nor FIFO). According to Microsoft this is done to improve performance.
So, what can we gather from this? First and foremost the term mutex is less well defined than the semaphore. Secondly,the actual implementations from RTOS to RTOS vary massively. I urge you to go back and look at your faviourite RTOS and work out what support, if any, you have for the mutex. I’d love to hear from people regarding mutual exclusion support (both semaphores and mutexes) for their RTOS of choice. If you’d like to contact me do so at nsc(at)acm.org.
Finally, Part 3 will look at a couple of problems the mutex doesn’t solve, and how these can be overcome. As part of that it will review the Basic Priority Inheritance Protcol and the Prority Ceiling Protocol.
At a later date I will also address the use of, and problems associted with, the semaphore being used for task synchronisation.
ENDNOTES

Please I do not want to get into the “that’s not a real-time OS” debate here – let’s save that for another day!
A number of people pointed out that Michael Barr (former editor of Embedded Systems Programming, now president of Netrino) has a good article about the differences between mutexes & semaphores at the following location: http://www.netrino.com/node/202. I urge you to read his posting as well.
Apologies about not having the atom feed sorted – this should all be working now

Posted on September 11th, 2009
» Feed to this thread
» Trackback

Mutex vs. Semaphores – Part 3 (final part): Mutual Exclusion Problems

As hopefully you can see from the previous posting, the mutex is a significantly safer mechanism to use for implementing mutual exclusion around shared resources. Nevertheless, there are still a couple of problems that use of the mutex (in preference to the semaphore) will not solve. These are:

Circular deadlock
Non-cooperation

Circular Deadlock
Circular deadlock, often referred to as the “deadly embrace” problem is a condition where two or more tasks develop a circular dependency of mutual exclusion. Simply put, one task is blocked waiting on a mutex owned by another task. That other task is also block waiting on a mutex held by the first task.
So how can this happen? Take as an example a small control system. The system is made up of three tasks, a low priority Control task, a medium priority System Identification (SI) task and a high priority Alarm task. There is an analogue input shared by the Control and the SI tasks, which is protected by a mutex. There is also an analogue output protected by a different mutex.

The Control task waits for mutexes ADC and DAC:

mutex_lock (ADC);
mutex_lock (DAC);
/* critical section */
mutex_unlock (ADC);
mutex_unlock (DAC);

The SI Task waits for mutexes DAC and ADC:
mutex_lock (DAC);
mutex_lock (ADC);
/* critical section */
mutex_unlock (DAC);
mutex_unlock (ADC);
Unfortunately, under certain timing conditions, this can lead to deadlock. In this example the Control task has locked the ADC, but before locking the DAC has been pre-empted by the higher priory SI task. The SI task then locks the DAC and tries to lock the ADC. The SI task is now blocked as the ADC is already owned by the Control task. The Control task now runs and tries to lock the DAC. It is blocked as the DAC is held by the SI task. Neither task can continue until the mutex is unlocked and neither mutex can be unlocked until either task runs – classic deadlock.

For circular deadlock to occur the following conditions must all be true:

A thread has exclusive use of resources (Mutual exclusion)
A thread can hold on to a resource(s) whilst waiting for another resource (Hold and wait)
A circular dependency of thread and resources is set up (Circular waiting)
A thread never releases a resource until it is completely finished with it (No resource preemption)

These conditions can be addressed in a number of ways. For example, a design policy may stipulate that if a task needs to lock more than one mutex it must either lock all or none.

Priority Ceiling Protocol

With the Priority Ceiling Protocol (PCP) method each mutex has a defined priority ceiling, set to that of the highest priority task which uses the mutex. Any task using a mutex executes at its own priority – until a second task attempts to acquire the mutex. At this point it has its priority raised to the ceiling value, preventing suspension and thus eliminating the “hold and wait” condition.
In the deadlock example shown before, the significant point is when the SI task tries to lock the DAC. Before that succeeded and lead to cyclic deadlock. However with a PCP mutex, both the ADC and DAC mutex will have a ceiling priority equal to the SI’s task priority. When the SI task tries to lock the DAC, then the run-time system will detect that the SI’s task priority is not higher than the priority of the locked mutex ADC. The run-time system suspends the SI task without locking the DAC mutex. The control task now inherits the priority of the SI task and resumes execution.

Non-cooperation

The last, but most important aspect of mutual exclusion covered in these ramblings relies on one founding principle: we have to rely on all tasks to access critical regions using mutual exclusion primitives. Unfortunately this is dependent on the design of the software and cannot be detected by the run-time system. This final problem was addressed by Tony Hoare, called the Monitor.

The Monitor

The monitor is a mechanism not typically supplied by the RTOS, but something the programmer tends to build (a notable exception is Ada95′s protected object mechanism). A monitor simply encapsulates the shared resource and the locking mechanism into a single construct (e.g. a C++ Object that encapsulates the mutex mechanism). Access to the shared resource, then, is through a controlled interface which cannot be bypassed (i.e. the application never explicitly calls the mutex, but calls upon access functions).
Finishing Off…
This goal of these initial postings is to demonstrate that common terms used in the real-time programming community are open to ambiguity and interpretation. Hopefully you should now be clear about the core differences between the Binary Semaphore, General (counting) Semaphore and the Mutex.
The underlying difference between the Semaphores and the Mutex is the Principle of Ownership. Given the principle of ownership a particular implementation of a mutex may support Recursion, Priority inheritanceand Death Detection.
ENDNOTE
An aspect of the mutex I haven’t covered here is that many operating systems support the concept of acondition variable. A condition variable allows a task to wait on a synchronization primitive within a critical region. The whole aspect Synchronization Patterns (e.g. semaphore as a signal) within the context of RTOSs will be the subject of my next posting.

Posted on October 5th, 2009
» Feed to this thread
» Trackback

When should one use a spinlock instead of mutex?

2013-07-22T00:04:00.002-07:00

he Theory

In theory, when a thread tries to lock a mutex and it does not succeed, because the mutex is already locked, it will go to sleep, immediately allowing another thread to run. It will continue to sleep until being woken up, which will be the case once the mutex is being unlocked by whatever thread was holding the lock before. When a tread tries to lock a spinlock and it does not succeed, it will continuously re-try locking it, until it finally succeeds; thus it will not allow another thread to take its place (however, the operating system will forcefully switch to another thread, once the CPU runtime quantum of the current thread has been exceeded, of course).

The Problem

The problem with mutexes is that putting threads to sleep and waking them up again are both rather expensive operations, they'll need quite a lot of CPU instructions and thus also take some time. If now the mutex was only locked for a very short amount of time, the time spent in putting a thread to sleep and waking it up again might exceed the time the thread has actually slept by far and it might even exceed the time the thread would have wasted by constantly polling on a spinlock. On the other hand, polling on a spinlock will constantly waste CPU time and if the lock is held for a longer amount of time, this will waste a lot more CPU time and it would have been much better if the thread was sleeping instead.

The Solution

Using spinlocks on a single-core/single-CPU system makes usually no sense, since as long as the spinlock polling is blocking the only available CPU core, no other thread can run and since no other thread can run, the lock won't be unlocked either. IOW, a spinlock wastes only CPU time on those systems for no real benefit. If the thread was put to sleep instead, another thread could have ran at once, possibly unlocking the lock and then allowing the first thread to continue processing, once it woke up again.

On a multi-core/multi-CPU systems, with plenty of locks that are held for a very short amount of time only, the time wasted for constantly putting threads to sleep and waking them up again might decrease runtime performance noticeably. When using spinlocks instead, threads get the chance to take advantage of their full runtime quantum (always only blocking for a very short time period, but then immediately continue their work), leading to much higher processing throughput.

The Practice

Since very often programmers cannot know in advance if mutexes or spinlocks will be better (e.g. because the number of CPU cores of the target architecture is unknown), nor can operating systems know if a certain piece of code has been optimized for single-core or multi-core environments, most systems don't strictly distinguish between mutexes and spinlocks. In fact, most modern operating systems have hybrid mutexes and hybrid spinlocks. What does that actually mean?

A hybrid mutex behaves like a spinlock at first on a multi-core system. If a thread cannot lock the mutex, it won't be put to sleep immediately, since the mutex might get unlocked pretty soon, so instead the mutex will first behave exactly like a spinlock. Only if the lock has still not been obtained after a certain amount of time (or retries or any other measuring factor), the thread is really put to sleep. If the same system runs on a system with only a single core, the mutex will not spinlock, though, as, see above, that would not be beneficial.

A hybrid spinlock behaves like a normal spinlock at first, but to avoid wasting too much CPU time, it may have a back-off strategy. It will usually not put the thread to sleep (since you don't want that to happen when using a spinlock), but it may decide to stop the thread (either immediately or after a certain amount of time) and allow another thread to run, thus increasing chances that the spinlock is unlocked (a pure thread switch is usually less expensive than one that involves putting a thread to sleep and waking it up again later on, though not by far).

Summary

If in doubt, use mutexes, they are usually the better choice and most modern systems will allow them to spinlock for a very short amount of time, if this seems beneficial. Using spinlocks can sometimes improve performance, but only under certain conditions and the fact that you are in doubt rather tells me, that you are not working on any project currently where a spinlock might be beneficial. You might consider using your own "lock object", that can either use a spinlock or a mutex internally (e.g. this behavior could be configurable when creating such an object), initially use mutexes everywhere and if you think that using a spinlock somewhere might really help, give it a try and compare the results (e.g. using a profiler), but be sure to test both cases, a single-core and a multi-core system before you jump to conclusions (and possibly different operating systems, if your code will be cross-platform).

saminer

2012-12-16T20:02:00.001-08:00

2012-06-21T23:09:00.002-07:00

GNU Make in Detail for Beginners

By Sarath Lakshman on June 9, 2012 in Developers, How-Tos, Tools / Apps · 2 Comments and 0 Reactions

Have you ever peeked into the source code of any of the applications you run every day? Ever used make install to install some application? You will see make in most projects. It enables developers to easily compile large and complex programs with many components. It’s also used for writing maintenance scripts based on timestamps. This article shows you how to have fun with make.

Large projects can contain thousands of lines of code, distributed in multiple source files, written by many developers and arranged in several subdirectories. A project may contain several component divisions. These components may have complex inter-dependencies — for example, in order to compile component X, you have to first compile Y; in order to compile Y, you have to first compile Z; and so on. For a large project, when a few changes are made to the source, manually recompiling the entire project each time is tedious, error-prone and time-consuming.

Make is a solution to these problems. It can be used to specify dependencies between components, so that it will compile components in the order required to satisfy dependencies. An important feature is that when a project is recompiled after a few changes, it will recompile only the files which are changed, and any components that are dependent on it. This saves a lot of time. Make is, therefore, an essential tool for a large software project.

Each project needs a Makefile — a script that describes the project structure, namely, the source code files, the dependencies between them, compiler arguments, and how to produce the target output (normally, one or more executables). Whenever the make command is executed, the Makefile in the current working directory is interpreted, and the instructions executed to produce the target outputs. The Makefile contains a collection of rules, macros, variable assignments, etc. (‘Makefile’ or ‘makefile’ are both acceptable.)

Installing GNU Make

Most distributions don’t ship make as part of the default installation. You have to install it, either using the package-management system, or by manually compiling from source. To compile and build from source, download the tarball, extract it, and go through the README file. (If you’re running Ubuntu, you can install make as well as some other common packages required for building from source, by running: sudo apt-get install build-essential.)

A sample project

To acquaint ourselves with the basics of make, let’s use a simple C “Hello world” project, and a Makefile that handles building of the target binary. We have three files (below): module.h, the header file that contains the declarations; module.c, which contains the definition of the function defined in module.h; and the main file, main.c, in which we call the sample_func() defined inmodule.c. Since module.h includes the required header files like stdio.h, we don’t need to include stdio.h in every module; instead, we just include module.h. Here, module.c andmain.c can be compiled as separate object modules, and can be linked by GCC to obtain the target binary.

module.h:

#include 

void sample_func();

module.c:

#include "module.h"

void sample_func()

{

    printf("Hello world!");

}

main.c:

#include "module.h"

void sample_func();

int main()

{

    sample_func();

    return 0;

}

The following are the manual steps to compile the project and produce the target binary:

slynux@freedom:~$ gcc -I . -c main.c # Obtain main.o

slynux@freedom:~$ gcc -I . -c module.c # Obtain module.o

slynux@freedom:~$ gcc main.o module.o -o target_bin #Obtain target binary

(-I is used to include the current directory (.) as a header file location.)

Writing a Makefile from scratch

By convention, all variable names used in a Makefile are in upper-case. A common variable assignment in a Makefile is CC = gcc, which can then be used later on as ${CC} or $(CC). Makefiles use # as the comment-start marker, just like in shell scripts.

The general syntax of a Makefile rule is as follows:

target: dependency1 dependency2 ...

[TAB] action1

[TAB] action2

    ...

Let’s take a look at a simple Makefile for our sample project:

all: main.o module.o

    gcc main.o module.o -o target_bin

main.o: main.c module.h

    gcc -I . -c main.c

module.o: module.c module.h

    gcc -I . -c module.c

clean:

    rm -rf *.o

    rm target_bin

We have four targets in the Makefile:

all is a special target that depends on main.o and module.o, and has the command (from the “manual” steps earlier) to make GCC link the two object files into the final executable binary.
main.o is a filename target that depends on main.c and module.h, and has the command to compile main.c to produce main.o.
module.o is a filename target that depends on module.c and module.h; it calls GCC to compile the module.c file to produce module.o.
clean is a special target that has no dependencies, but specifies the commands to clean the compilation outputs from the project directories.

You may be wondering why the order of the make targets and commands in the Makefile are not the same as that of the manual compilation commands we ran earlier. The reason is so that the easiest invocation, by just calling the make command, will result in the most commonly desired output — the final executable. How does this work?

The make command accepts a target parameter (one of those defined in the Makefile), so the generic command line syntax is make . However, make also works if you do not specify any target on the command line, saving you a little typing; in such a case, it defaults to the first target defined in the Makefile. In our Makefile, that is the target all, which results in the creation of the desired executable binary target_bin!

Makefile processing, in general

When the make command is executed, it looks for a file named makefile or Makefile in the current directory. It parses the found Makefile, and constructs a dependency tree. Based on the desired make target specified (or implied) on the command-line, make checks if the dependency files of that target exist. And (for filename targets — explained below) if they exist, whether they are newer than the target itself, by comparing file timestamps.

Before executing the action (commands) corresponding to the desired target, its dependencies must be met; when they are not met, the targets corresponding to the unmet dependencies are executed before the given make target, to supply the missing dependencies.

When a target is a filename, make compares the timestamps of the target file and its dependency files. If the dependency filename is another target in the Makefile, make then checks the timestamps of that target’s dependencies. It thus winds up recursively checking all the way down the dependency tree, to the source code files, to see if any of the files in the dependency tree are newer than their target filenames. (Of course, if the dependency files don’t exist, then make knows it must start executing the make targets from the “lowest” point in the dependency tree, to create them.)

If make finds that files in the dependency tree are newer than their target, then all the targets in the affected branch of the tree are executed, starting from the “lowest”, to update the dependency files. When make finally returns from its recursive checking of the tree, it completes the final comparison for the desired make target. If the dependency files are newer than the target (which is usually the case), it runs the command(s) for the desired make target.

This process is how make saves time, by executing only commands that need to be executed, based on which of the source files (listed as dependencies) have been updated, and have a newer timestamp than their target.

Now, when a target is not a filename (like all and clean in our Makefile, which we called “special targets”), make obviously cannot compare timestamps to check whether the target’s dependencies are newer. Therefore, such a target is always executed, if specified (or implied) on the command line.

For the execution of each target, make prints the actions while executing them. Note that each of the actions (shell commands written on a line) are executed in a separate sub-shell. If an action changes the shell environment, such a change is restricted to the sub-shell for that action line only. For example, if one action line contains a command like cd newdir, the current directory will be changed only for that line/action; for the next line/action, the current directory will be unchanged.

Processing our Makefile

After understanding how make processes Makefiles, let’s run make on our own Makefile, and see how it is processed to illustrate how it works. In the project directory, we run the following command:

slynux@freedom:~$ make

gcc -I . -c main.c

gcc -I . -c module.c

gcc main.o module.o -o target_bin

What has happened here?

When we ran make without specifying a target on the command line, it defaulted to the first target in our Makefile — that is, the target all. This target’s dependencies are module.o and main.o. Since these files do not exist on our first run of make for this project, make notes that it must execute the targets main.o and module.o. These targets, in turn, produce the main.o andmodule.o files by executing the corresponding actions/commands. Finally, make executes the command for the target all. Thus, we obtain our desired output, target_bin.

If we immediately run make again, without changing any of the source files, we will see that only the command for the target all is executed:

slynux@freedom:~$ make

gcc main.o module.o -o target_bin

Though make checked the dependency tree, neither of the dependency targets (module.o andmain.o) had their own dependency files bearing a later timestamp than the dependency target filename. Therefore, make rightly did not execute the commands for the dependency targets. As we mentioned earlier, since the target all is not a filename, make cannot compare file timestamps, and thus executes the action/command for this target.

Now, we update module.c by adding a statement printf("\nfirst update"); inside thesample_func() function. We then run make again:

slynux@freedom:~$ make

gcc -I . -c module.c

gcc main.o module.o -o target_bin

Since module.c in the dependency tree has changed (it now has a later timestamp than its target, module.o), make runs the action for the module.o target, which recompiles the changed source file. It then runs the action for the all target.

We can explicitly invoke the clean target to clean up all the generated .o files and target_bin:

$ make clean

rm -rf *.o

rm target_bin

More bytes on Makefiles

Make provides many interesting features that we can use in Makefiles. Let’s look at the most essential ones.

Dealing with assignments

There are different ways of assigning variables in a Makefile. They are (type of assignment, followed by the operator in parentheses):

Simple assignment (:=)

We can assign values (RHS) to variables (LHS) with this operator, for example: CC := gcc. With simple assignment (:=), the value is expanded and stored to all occurrences in the Makefile when its first definition is found.

For example, when a CC := ${GCC} ${FLAGS} simple definition is first encountered, CC is set togcc -W and wherever ${CC} occurs in actions, it is replaced with gcc -W.

Recursive assignment (=)

Recursive assignment (the operator used is =) involves variables and values that are not evaluated immediately on encountering their definition, but are re-evaluated every time they are encountered in an action that is being executed. As an example, say we have:

GCC = gcc

FLAGS = -W

With the above lines, CC = ${GCC} {FLAGS} will be converted to gcc -W only when an action like ${CC} file.c is executed somewhere in the Makefile. With recursive assignation, if the GCC variable is changed later (for example, GCC = c++), then when it is next encountered in an action line that is being updated, it will be re-evaluated, and the new value will be used; ${CC}will now expand to c++ -W.

We will also have an interesting and useful application further in the article, where this feature is used to deal with varying cases of filename extensions of image files.

Conditional assignment (?=)

Conditional assignment statements assign the given value to the variable only if the variable does not yet have a value.

Appending (+=)

The appending operation appends texts to an existing variable. For example:

CC = gcc

CC += -W

CC now holds the value gcc -W.

Though variable assignments can occur in any part of the Makefile, on a new line, most variable declarations are found at the beginning of the Makefile.

Using patterns and special variables

The % character can be used for wildcard pattern-matching, to provide generic targets. For example:

%.o: %.c

[TAB] actions

When % appears in the dependency list, it is replaced with the same string that was used to perform substitution in the target.

Inside actions, we can use special variables for matching filenames. Some of them are:

$@ (full target name of the current target)
$? (returns the dependencies that are newer than the current target)
$* (returns the text that corresponds to % in the target)
$< (name of the first dependency)
$^ (name of all the dependencies with space as the delimiter)

Instead of writing each of the file names in the actions and the target, we can use shorthand notations based on the above, to write more generic Makefiles.

Action modifiers

We can change the behaviour of the actions we use by prefixing certain action modifiers to the actions. Two important action modifiers are:

- (minus) — Prefixing this to any action causes any error that occurs while executing the action to be ignored. By default, execution of a Makefile stops when any command returns a non-zero (error) value. If an error occurs, a message is printed, with the status code of the command, and noting that the error has been ignored. Looking at the Makefile from our sample project: in the clean target, the rm target_bin command will produce an error if that file does not exist (this could happen if the project had never been compiled, or if make cleanis run twice consecutively). To handle this, we can prefix the rm command with a minus, to ignore errors: -rm target_bin.
@ (at) suppresses the standard print-action-to-standard-output behaviour of make, for the action/command that is prefixed with @. For example, to echo a custom message to standard output, we want only the output of the echo command, and don’t want to print the echo command line itself. @echo Message will print “Message” without the echo command line being printed.

Use PHONY to avoid file-target name conflicts

Remember the all and clean special targets in our Makefile? What happens when the project directory has files with the names all or clean? The conflicts will cause errors. Use the .PHONYdirective to specify which targets are not to be treated as files — for example: .PHONY: all clean.

Simulating make without actual execution

At times, maybe when developing the Makefile, we may want to trace the make execution (and view the logged messages) without actually running the actions, which is time consuming. Simply use make -n to do a “dry run”.

Using the shell command output in a variable

Sometimes we need to use the output from one command/action in other places in the Makefile — for example, checking versions/locations of installed libraries, or other files required for compilation. We can obtain the shell output using the shell command. For example, to return a list of files in the current directory into a variable, we would run: LS_OUT = $(shell ls).

Nested Makefiles

Nested Makefiles (which are Makefiles in one or more subdirectories that are also executed by running the make command in the parent directory) can be useful for building smaller projects as part of a larger project. To do this, we set up a target whose action changes directory to the subdirectory, and invokes make again:

subtargets:

    cd subdirectory && $(MAKE)

Instead of running the make command, we used $(MAKE), an environment variable, to provide flexibility to include arguments. For example, if you were doing a “dry run” invocation: if we used the make command directly for the subdirectory, the simulation option (-n) would not be passed, and the commands in the subdirectory’s Makefile would actually be executed. To enable use of the -n argument, use the $(MAKE) variable.

Now let’s improve our original Makefile using these advanced features:

CC = gcc # Compiler to use

OPTIONS = -O2 -g -Wall # -g for debug, -O2 for optimise and -Wall additional messages

INCLUDES = -I . # Directory for header file

OBJS = main.o module.o # List of objects to be build

.PHONY: all clean # To declare all, clean are not files

all: ${OBJS}

    @echo "Building.." # To print "Building.." message

    ${CC} ${OPTIONS} ${INCLUDES} ${OBJS} -o target_bin 

%.o: %.c  # % pattern wildcard matching

    ${CC} ${OPTIONS} -c $*.c ${INCLUDES}

list:

    @echo $(shell ls) # To print output of command 'ls'

clean:

    @echo "Cleaning up.."

    -rm -rf *.o # - prefix for ignoring errors and continue execution

    -rm target_bin

Run make on the modified Makefile and test it; also run make with the new list target. Observe the output.

Make in non-compilation contexts

I hope you’re now well informed about using make in a programming context. However, it’s also useful in non-programming contexts, due to the basic behaviour of checking the modification timestamps of target files and dependencies, and running the specified actions when required. For example, let’s write a Makefile that will manage an image store for us, doing thumbnailing when required. Our scenario is as follows:

We have a directory with two subdirectories, images and thumb.
The images subdirectory contains many large image files; thumb contains thumbnails of the images, as .jpg files, 100x100px in image size.
When a new image is added to the images directory, creation of its thumbnail in the thumbdirectory should be automated. If an image is modified, its thumbnail should be updated.
The thumbnailing process should only be done for new or updated images, and not images that have up-to-date thumbnails.

This problem can be solved easily by creating a Makefile in the top-level directory, as follows:

FILES = $(shell  find images -type f -iname "*.jpg" | sed 's/images/thumb/g')

CONVERT_CMD = convert -resize "100x100" $< $@

MSG = @echo "\nUpdating thumbnail" $@

all: ${FILES}

thumb/%.jpg: images/%.jpg

    $(MSG)

    $(CONVERT_CMD)

thumb/%.JPG: images/%.JPG

    $(MSG)

    $(CONVERT_CMD)

clean:

    @echo Cleaning up files..

    rm -rf thumb/*.jpg thumb/*.JPG

In the above Makefile, FILES = $(shell find images -type f -iname "*.jpg" | sed 's/images/thumb/g') is used to generate a list of dependency filenames. JPEG files could have the extension .jpg or .JPG (that is, differing in case). The -iname parameter to find (find images -type f -iname "*.jpg") will do a case-insensitive search on the names of files, and will return files with both lower-case and upper-case extensions — for example, images/1.jpg,images/2.jpg, images/3.JPG and so on. The sed command replaces the text “images” with “thumb”, to get the dependency file path.

When make is invoked, the all target is executed first. Since FILES contains a list of thumbnail files for which to check the timestamp (or if they exist), make jumps down to the thumb/%.jpgwildcard target for each thumbnail image file name. (If the extension is upper-case, that is,thumb/3.JPG, then make will look for, and find, the second wildcard target, thumb/%.JPG.)

For each thumbnail file in the thumb directory, its dependency is the image file in the imagesdirectory. Hence, if any file (that’s expected to be) in the thumb directory does not exist, or its timestamp is older than the dependency file in the images directory, the action (calling$(CONVERT_CMD) to create a thumbnail) is run.

Using the features we described earlier, CONVERT_CMD is defined before targets are specified, but it uses recursive assignment. Hence, the input and target filenames passed to the convert command are substituted from the first dependency ($<) and the target ($@) every time the action is invoked, and thus will work no matter from which action target (thumb/%.JPG orthumb/%.jpg) the action is invoked.

Naturally, the “Updating thumbnail” message is also defined using recursive assignment for the same reasons, ensuring that $(MSG) is re-evaluated every time the actions are executed, and thereby able to cope with variations in the case of the filename extension.

slynux@freedom:~$ make

Updating thumbnail 1.jpg

convert -resize "100x100" images/1.jpg thumb/1.jpg

 Updating thumbnail 4.jpg

convert -resize "100x100" images/4.jpg thumb/4.jpg

If I edit 4.jpg in images and rerun make, since only 4.jpg‘s timestamp has changed, a thumbnail is generated for that image:

slynux@freedom:~$ make

Updating thumbnail 4.jpg

convert -resize "100x100" images/4.jpg thumb/4.jpg

Writing a script (shell script or Python, etc) to maintain image thumbnails by monitoring timestamps would have taken many lines of code. With make, we can do this in just 8 lines of Makefile. Isn’t make awesome?

That’s all about the basics of using the make utility. Happy hacking till we meet again!

This article was originally published in September 2010 issue of the print magazine.

setup of IP camera

2012-05-23T09:01:00.001-07:00

http://www.youtube.com/watch?v=ZU_xobdKQOs

Vim plugin

2012-05-10T22:35:00.001-07:00

http://www.thegeekstuff.com/2009/04/ctags-taglist-vi-vim-editor-as-sourece-code-browser/

Ctags and Taglist: Convert Vim Editor to Beautiful Source Code Browser for Any Programming Language

by SATHIYAMOORTHY on APRIL 20, 2009

Photo Courtesy: mint imperial

This article is part of the on-going Vi / Vim Tips and Tricks series. As a programmer or system administrator, you will be constantly browsing source codes and shell scripts.

Following are some typical activities that you may perform while browsing a source code file:

Navigating to the function definition by specifying the function name.
Navigating to the function definition from ‘function call’.
Returning back again to function call from the definition.
Viewing the prototype/signature of functions or variables.
Viewing the number of functions in a file, etc.,

In this article, let us review how to perform the above activities efficiently in Vim editor usingctags and taglist plugin.

The techniques mentioned in this article using Vim editor can be used for any programming language.

I. Ctags Package Install and Configure

Step 1: Installing ctags Package

# apt-get install exuberant-ctags

(or)

# rpm -ivh ctags-5.5.4-1.i386.rpm
warning: ctags-5.5.4-1.i386.rpm: V3 DSA signature: NOKEY, key ID db42a60e
Preparing...          ########################################### [100%]
   1:ctags            ########################################### [100%]

Step 2: Generating ctags on your source code

Go to the directory where your source code is located. In the example below, I have stored all my C programming source code under ~/src directory.

# cd ~/src

# ctags *.c

The ctags command will create a filename tags the will contain all required information (tags) about the *.c program files. Following is partial output of the tags entries in the ctags file.

# cat tags
AddAcl  dumputils.c     /^AddAcl(PQExpBuffer aclbuf, const char *keyword)$/;"   f       file:
ArchiveEntry    pg_backup_archiver.c    /^ArchiveEntry(Archive *AHX,$/;"        f
AssignDumpId    common.c        /^AssignDumpId(DumpableObject *dobj)$/;"        f

II. 4 Powerful Ctags Usages inside Vim Editor

1. Navigate to function definition by specifying the function name using :ta

In the example below, :ta main will take you to the main function definition inside the mycprogram.c

# vim mycprogram.c
:ta main

By using this facility you can navigate to any function definition by specifying the function name.

2. Navigating to the function definition from ‘function call’ using Ctrl + ]

When the cursor is under the function call, then press CTRL + ] to go to the function definition. In the following example, when the cursor is in the function call ssh_xcalloc, pressing Ctrl + ] will take you to the ssh_xcalloc function definition.

# vim mycprogram.c
            av = ssh_xcalloc(argc, sizeof(char *));

Note: If the ctags couldn’t find that function, you’ll get the following message in the vim status bar at the bottom: E426 tag not found ssh_xcalloc

3. Returning back again to function call from the definition using Ctrl + t

Press CTRL + t which will take back to the function call again.

4. Navigating through a list of function names which has the similar names

In this example, :ta will go to the function definition whose name starts with get, and also builds a list to navigate with the relevant functions.

# vim mycprogram.c

:ta /^get

Following vim commands can be used to navigate through relevant functions

:ts – shows the list.
:tn – goes to the next tag in that list.
:tp - goes to the previous tag in that list.
:tf – goes to the function which is in the first of the list.
:tl – goes to the function which is in the last of the list.

III. Taglist Plugin: Vim Editor as Ultimate Source Code Browser

The above Ctags might have not given a source code browsing feeling, as it is driven by commands instead of visually browsing the code. So if you want to navigate through the source as like navigating in the file browser, you need to use vim taglist plugin which makes vim as a source code browser.

Author of the vim taglist plugin Yegappan Lakshmanan, says about it as

The “Tag List” plugin is a source code browser plugin for Vim and provides an overview of the structure of source code files and allows you to efficiently browse through source code files for different programming languages.

Step 1: Download the Vim Taglist plugin

Download it from from vim.org website as shown below.

$ cd /usr/src

$ wget -O taglist.zip http://www.vim.org/scripts/download_script.php?src_id=7701

Step 2: Install the TagList Vim Plugin

$ mkdir ~/.vim # if the directory does not exist already

$ cd ~/.vim

$ unzip /usr/src/taglist.zip
Archive:  /usr/src/taglist.zip
  inflating: plugin/taglist.vim
  inflating: doc/taglist.txt

Step 3: Enable the plugin in the ~/.vimrc

Add the following line to the ~/.vimrc to enable the plugin for Vim editor.

$ vim ~/.vimrc
filetype plugin on

Pre-Requisite: ctags should be installed to use taglist plugin. But it is not a must to generate the tag list manually by ctags command for using taglist plugin.

IV. 5 Powerful Features of Taglist Vim Plugin

1. Open the Tag List Window in Vim using :TlistOpen

# vim mycprogram.c
:TlistOpen

From the vim editor, execute :TlistOpen as shown above, which opens the tag list window with the tags of the current file as shown in the figure below.

Fig: Vim – Source Code Tag/Function List Windows

2. Jump to the Function Definition inside a source code

By clicking on the function name in the left panel, you would be able to go to the definition of the function as shown in the Figure below.

Fig: Jump to a function definition quickly

Apart form jumping to the function names quickly, you can jump to classes, structures, variables, etc., by clicking on the corresponding values from the tag-browser in the left hand side.

3. Jump to the function definition which is in another source file

When you are going through a function in a source file and would want to go to the function definition which is in another file, you can do this in two different methods.

Method 1:

If you had the ctags generated for that file, when the cursor is in the function call pressing CTRL + ] will take you to the function definition. And automatically the tag list window will show the tags for that newly opened file.

Method 2:

Open another file also in the same vim session which will update the tag list window with the information about that file. Search for that function name in the tag list window, and by pressing on that function name in the tag list window you can go to the function definition.

4. Viewing the prototype/signature of functions or variables.

Press ‘space’ in the function name or in the variable name in the tag list window to show the prototype (function signature) of it in the VIM status bar as shown below. In the example below, click on selectDumpableTable function from the Tag-window and press space-bar, which displays the function signature for selectDumptableTable function in the bottom Vim Status bar.

Fig: Display Function signature at the Vim Status Bar

5. Viewing the total number of functions or variables in a source code file

press ‘space’ in the tag type in the tag list window, which shows the count of it. In the example below, when the cursor is at ‘function’ press space, which will display the total number of functions in the current source code.

Fig: Display the total number of functions available in the source code

For effectively writing new source code files using Vim, please refer to our earlier articles:

screen man page

2012-05-10T02:43:00.005-07:00

screen Multiplex a physical terminal between several processes (typically interactive shells). Syntax: Start a screen session: screen [ -options ] [ cmd [args] ] Resume a detached screen session: screen -r [[pid.]tty[.host]] screen -r sessionowner/[[pid.]tty[.host]] Options: -A -[r|R] Adapt all windows to the new display width & height. -c file Read configuration file instead of .screenrc -d (-r) Detach the elsewhere running screen (and reattach here). -dmS name Start as daemon: Screen session in detached mode. -D (-r) Detach and logout remote (and reattach here). -D -RR Do whatever is needed to Reattach a screen session. -d -m Start in "detached" mode. Useful for system startup scripts. -D -m Start in "detached" mode, & don't fork a new process. -list List our SockDir and do nothing else (-ls) -r Reattach to a detached screen process. -R Reattach if possible, otherwise start a new session. -t title Set title. (window's name). -U Tell screen to use UTF-8 encoding. -x Attach to a not detached screen. (Multi display mode). -X Execute cmd as a screen command in the specified session. Interactive commands (default key bindings): Control-a ? Display brief help Control-a " List all windows for selection Control-a ' Prompt for a window name or number to switch to. Control-a 0 Select window 0 Control-a 1 Select window 1 ... ... Control-a 9 Select window 9 Control-a A Accept a title name for the current window. Control-a b Send a break to window Control-a c Create new window running a shell Control-a C Clear the screen Control-a d Detach screen from this terminal. Control-a D D Detach and logout. Control-a f Toggle flow on, off or auto. Control-a F Resize the window to the current region size. Control-a h Write a hardcopy of the current window to file "hardcopy.n" Control-a H Begin/end logging of the current window to file "screenlog.n" Control-a i Show info about this window. Control-a k Kill (Destroy) the current window. Control-a l Fully refresh current window Control-a M Monitor the current window for activity {toggle on/off} Control-a n Switch to the Next window Control-a N Show the Number and Title of window Control-a p Switch to the Previous window Control-a q Send a control-q to the current window(xon) Control-a Q Delete all regions but the current one.(only) Control-a r Toggle the current window's line-wrap setting(wrap) Control-a s Send a control-s to the current window(xoff) Control-a w Show a list of windows (windows) Control-a x Lock this terminal (lockscreen) Control-a X Kill the current region(remove) Control-a Z Reset the virtual terminal to its "power-on" values Control-a Control-\ Kill all windows and terminate screen(quit) Control-a : Enter command line mode(colon) Control-a [ Enter copy/scrollback mode(copy) Control-a ] Write the contents of the paste buffer to stdin(paste) Control-a _ Monitor the current window for inactivity {toggle on/off} Control-a * Show a listing of all currently attached displays. When screen is called, it creates a single window with a shell in it (or the specified command) and then gets out of your way so that you can use the program as you normally would. Then, at any time, you can: Create new (full-screen) windows with other programs in them (including more shells) Kill existing windows View a list of windows Switch between windows - all windows run their programs completely independent of each other. Programs continue to run when their window is currently not visible and even when the whole screen session is detached from the user's terminal. The interactive commands above assume the default key bindings. You can modify screen’s settings by creating a ~/.screenrc file in your home directory. This can change the default keystrokes, bind function keys F11, F12 or even set a load of programs/windows to run as soon as you start screen. Attaching and Detaching Once you have screen running, switch to any of the running windows and type Control-a d. this will detach screen from this terminal. Now, go to a different machine, open a shell, ssh to the machine running screen (the one you just detached from), and type: % screen -r This will reattach to the session. Just like magic, your session is back up and running, just like you never left it. Exiting screen completely Screen will exit automatically when all of its windows have been killed. Close whatever program is running or type `Exit ' to exit the shell, and the window that contained it will be killed by screen. (If this window was in the foreground, the display will switch to the previous window) When none are left, screen exits. This page is just a summary of the options available, type man screen for more. "Growing old is mandatory, but growing up is optional" - Motto of the Silver Screen Saddle Pals ======================================== Using screen (virtual terminal multiplexer) What is screen? “Screen is a full-screen window manager that multiplexes a physical terminal between several processes (typically interactive shells).” (from man page) In every-day use you just type $ screen and it seems that nothing happens. :) In fact a program is run that manages multiple bash processes and allows doing cool stuff in console(s) without having to run X. Basics Ctrl+a is a basic command that allows you to control screen. After you've pressed Ctrl+a your input is not being sent to current console, but to the screen itself. That's where you issue one-letter commands. (and more, but let's not get you confused) basic commands Ctrl+a c - create new console Ctrl+a n - switch to next console (it loops) Ctrl+a p - switch to previous console (it loops) Ctrl+a a - send Ctrl+a combination to the program, I didn't want to call screen Ctrl+a k - kill current console (asks to confirm)(ends screen when last console is killed) Ctrl+a d - detach - exits screen but leaves consoles and theri processes running For jornada it might be comfortable to bind winkey to do Ctrl+a. I'll expand the tutorial when I find the best way to do it. Copy and paste [[awesome]] You like using links browser in text mode, but you hate having to start X or use wget to copy some text from a page? Screen is the answer! Ctrl+a [[ - switch to copy mode - then use arrows to move cursor - press Enter to start selection - move cursor to the end - press Enter again Now switch to another console with your awesome script being developed in an editor or just jump to a textfield on a page… Ctrl+a ]] - pastes the copied text Useful for transporting data between two separate instances of screen or for using copied text as an input file for programs: Ctrl+a > - writes copied buffer to a file given in config (/tmp/screen-exchange by default, but don't go looking through options - it'll tell you where it writes) Ctrl+a < - loads the file to buffer Splitting screen You can split your screen and display two (or more, but…) consoles at the same time. Screen avaliable in jlime repos supports only horizontal splitting, so I won't mention the vertical splitting keys. Ctrl+a S - does the split (S is Shift+s and it has to be capital S) - new screen region is created - you probably want to press //Ctrl+a c// to start a new console in there Ctrl+a Tab - switches between visible splits Ctrl+a :resize (Enter) - prompts for number of lines and resizes current split Ctrl+a X - removes current split Monitoring activity If you work in one console and running something in another you might want to monitor it. Ctrl+a M - starts monitoring current console for changes (Will inform you when a program outputs something new. Good for IM clients) Ctrl+a _ - start monitoring current console for silence (Will inform you when a program stops outputting new stuff. Good for compiling or downloading with wget) Sessions and attaching Mostly useful when working on a remote machine with screen, but you might want to know this. When you loose a connection or leave screen with Ctrl+a d your processes stay there. You might want to get to them again I suppose :) $ screen -ls There is a screen on: 21209.pts-0.computername (Detached) 1 Socket in /var/run/screen/S-username. To get back to the running screen type $ screen -r 21209 21209 in both examples above is a PID of the screen process. ===================================== http://snipplr.wordpress.com/2012/04/07/my-screenrc-with-custom-hardstatus-and-easy-switching-between-screens/ screen setup with custom hard status and dialog menu Posted on April 7, 2012 The following set of scripts produce a nice screen setup along with a dialog menu for the most common tasks. This is how it looks like And this is how it’s done. Please see inline comments for details. 01 #!/bin/bash 02 ## use shift-left/right to switch between windows 03 ## use ctrl-n to add new shellwindow 04 ## use shift-PgUp/PgDown for scrolling history hit esc to stop 05 ## use ctrl-a-k for killing a window 06 ## mark area with space, end marking with space, paste with ctrl-a-] 07 setenv TERM xterm 08 09 #kill startup messes 10 startup_message off 11 12 # detach on hangup 13 autodetach on 14 15 # define a bigger scrollback, default is 100 lines 16 defscrollback 4096 17 18 # shell 19 shell -bash 20 21 #make scrollbar work 22 termcapinfo xterm ti@:te@ 23 24 defmonitor on # turn monitoring on 25 activity "%" # tell me when stuff happens! 26 27 # Make shift-PgUp and shift-PgDn work like they do in xterm. (Note that this 28 # requires xterm to be configured to pass those keys through, and not try to 29 # act on them itself.) 30 bindkey "^[O2A" eval "copy" "stuff ^b" 31 bindkey -m "^[O2A" stuff ^u 32 bindkey -m "^[O2B" stuff ^d 33 34 bindkey "^[O2D" prev 35 bindkey "^[O2C" next 36 37 # ctrl-N for new window 38 bindkey "^N" screen 39 40 # ctrl-a-b to copy selection to osx-clipboard 41 #bind b eval "writebuf" "exec sh -c 'pbcopy < /tmp/screen-exchange'" 42 43 # Window numbering starts at 1, not 0. 44 bind c screen 1 45 bind 0 select 10 46 47 # Run everything in UTF-8. 48 defutf8 on 49 # If a window goes unresponsive, don't block the whole session waiting for it. 50 nonblock on 51 52 # An alternative hardstatus to display a bar at the bottom listing the 53 # windownames and highlighting the current windowname in blue. (This is only 54 # enabled if there is no hardstatus setting for your terminal) 55 # see http://www.debian-administration.org/articles/560 56 hardstatus on 57 hardstatus alwayslastline 58 hardstatus string "%{.bW}%-w%{.rW}%n %t%{-}%+w %=%{..G} %H %{..Y} %m/%d %C%a " 59 60 screen -t selector sh screen-selector.sh I use this via screen -c selector-screenrc. The helper script for initializing a screen session looks like this and would either connect to an existing one or create a new one. 1 #!/bin/bash 2 3 screenpid=`ps x|grep -E '(.*)SCREEN(.*)selector-screenrc\$'|awk '{print \$1}'|head -1` 4 if [ $screenpid -gt 0 ]; then 5 screen -x $screenpid -c selector-screenrc 6 else 7 screen -c selector-screenrc 8 fi The screen-selector.sh file is a bonus and provides a dialog menu for frequently used commands. It looks like this 01 #!/bin/bash 02 03 while [ 1 ]; do 04 05 select=`/opt/local/bin/dialog --stdout --menu "select task" 20 60 13 \`cat tasks | tr '\040' '_' | tr '\012' '\040'\`` 06 07 echo "selected $select" 08 09 if [ ! -z $select ]; then 10 11 echo $select 12 13 command=`grep $select tasks|awk 'BEGIN{FS=OFS="\t"}{print \$2}'|tr -d "\""` 14 15 echo "executing command \"$command\"" 16 17 $command 18 # sleep 2 19 else 20 exit 0 21 fi 22 23 done The “tasks” file holds a simple list of tasks/commands. See the example below. 1 su "screen -t rootshell sudo su -" 2 newshell "screen -t shell"

Data structure

2012-05-08T01:02:00.003-07:00

http://www.data-structure-definition.blogspot.in/

cordless phone

2012-04-13T01:29:00.000-07:00

http://www.vijaypadiyar.in/blog/2011/04/how-to-choose-the-right-cordless-phone

screen utility

2012-04-11T02:06:00.000-07:00

1. http://magazine.redhat.com/2007/09/27/a-guide-to-gnu-screen/

netapp

2012-02-29T01:21:00.001-08:00

1. mbuf and sk buff
2. read or load , which is costely
3. const int a;
int const a;
const int const a;
what is difference between above 3
4. spanning tree

Mobile options

2012-02-21T20:42:00.001-08:00

1. http://androidadvices.com/tether-galaxy-s2-i9100-wifi-hotspot/

kernel space and user spcase

2012-02-05T16:15:00.000-08:00

http://www.ibm.com/developerworks/linux/library/l-kernel-memory-access/ : good must read

http://people.ee.ethz.ch/~arkeller/linux/kernel_user_space_howto.html#s5 : must read

http://www.wil.cx/matthew/lca2003/paper.pdf : must read

Neeraj Gupta

TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast Recovery Algorithms

1. Slow Start

2. Congestion Avoidance

3. Fast Retransmit

4. Fast Recovery

5. Security Considerations

TCP : Fast Retransmit

LCM findFirstCommonAncestor

Height of a Tree

Write a C Program to Find the Maximum Depth or Height of a Tree

Interview Question at narus

Linux kernal flow : v imp

kernel_flow

Contents

Layer 5: Session layer (sockets and files)

Layer 4: Transport layer (TCP)

Layer 3: Network layer (IPv4)

Layer 2: Link layer (e.g. Ethernet)

Layer 2: Link layer (e.g. Ethernet)

Layer 3: Network layer (IPv4, ARP)

Layer 4: Transport layer (TCP)

Layer 5: Session layer (sockets and files)

Networking in the Linux Kernel

Zero Copy I: User-Mode Perspective

Zero Copy I: User-Mode Perspective

What are high memory and low memory on Linux?

What is difference between User space and Kernel space

NAT DSlite 6rd NAT64

Network components

Barracuda Networks Interview

Mutex vs. Semaphores

When should one use a spinlock instead of mutex?

saminer

GNU Make in Detail for Beginners

Installing GNU Make

A sample project

Writing a Makefile from scratch

Makefile processing, in general

Processing our Makefile

More bytes on Makefiles

Dealing with assignments

Simple assignment (:=)

Recursive assignment (=)

Conditional assignment (?=)

Appending (+=)

Using patterns and special variables

Action modifiers

Use PHONY to avoid file-target name conflicts

Simulating make without actual execution

Using the shell command output in a variable

Nested Makefiles

Make in non-compilation contexts

setup of IP camera

Vim plugin

Ctags and Taglist: Convert Vim Editor to Beautiful Source Code Browser for Any Programming Language

I. Ctags Package Install and Configure

Step 1: Installing ctags Package

Step 2: Generating ctags on your source code

II. 4 Powerful Ctags Usages inside Vim Editor

1. Navigate to function definition by specifying the function name using :ta

2. Navigating to the function definition from ‘function call’ using Ctrl + ]

3. Returning back again to function call from the definition using Ctrl + t

4. Navigating through a list of function names which has the similar names

III. Taglist Plugin: Vim Editor as Ultimate Source Code Browser

Step 1: Download the Vim Taglist plugin

Step 2: Install the TagList Vim Plugin

Step 3: Enable the plugin in the ~/.vimrc

IV. 5 Powerful Features of Taglist Vim Plugin

1. Open the Tag List Window in Vim using :TlistOpen

2. Jump to the Function Definition inside a source code

3. Jump to the function definition which is in another source file

Method 1:

Method 2:

4. Viewing the prototype/signature of functions or variables.

5. Viewing the total number of functions or variables in a source code file

Recommended Reading

screen man page

Data structure

cordless phone