Saturday, January 25, 2014

Packet Headers


When I am working with libnet, libpcap or trying to troubleshoot network applications with Wireshark,  I consistently refer to the web for information on packet headers. I thought that it may be a helpful to put all that information on one page to make it easy to find. I hope others will find this quick reference useful as well.
If you have any suggestions on how to present the headers better than the images below, please let me know. 
If the images are too small to read, you can download the image or enlarge them in your browser.

Ethernet Header:

IPv4 Header:

TCP Header:


UDP Header:

ICMP Header:



Sunday, January 19, 2014

Linked List Example in C


A linked list is a data structure that consists of a group of nodes which are linked together. These are one of the simplest and most common data structures for C programs. One of the biggest advantages that linked lists have is they are efficient at inserting and deleting elements within the sequence. The biggest drawback of linked list is you generally have to traverse the list to find particular nodes or to get the number of nodes in the list.

There are several varieties of linked lists like singly linked, doubly linked and multiply linked. We will be using singly linked lists in this blog as we create various networking tools therefore, in this first tutorial, we will build a singly linked list library that we can integrate with our networking code. While the code for this library could be optimized and compacted, I feel that it is more important to make code readable when learning therefore the code for this library and most of the code in this blog will be written with functionality and readability as the primary objectives.

In a singly linked list each node has one or more data fields and a “next” field that points to the next node in the list. The preceding image shows how this works where the “next” element contains a pointer to the next node in the list.



You will be able to see how the linked list works as we go though the code but first lets take a quick look at the header file for our linked list library:

#ifndef LinkedListTest_linkedlistlib_h
#define LinkedListTest_linkedlistlib_h

struct node
{
   int num;
   char name[16];
   struct node *next;
};


struct node *buildnode(int num, char *name);
int addnode(struct node *head, struct node *add);
int length(struct node* head);
void deletelist(struct node **head);
struct node *searchnode(struct node *head, char *name);
int removenode(struct node **head, struct node *remove);

#endif


We begin by defining the structure that will hold our data. This structure can contain whatever data elements you need but you will need to keep the struct node *next element because it points to the next node in the list.
Next we define six functions that we will be implementing for our library. These functions are:
  • struct node *buildnode(int num, char *name) – This is a convenience method that will build the node given the values pass in. This function and the searchnode() function are the two functions that we will need to change when we add this library to our projects.
  • int addnode(struct node *head, struct node *add) – This function will add a node to the end of our list. The head node is the first node in our structure while the add node is the node to add. This function will return the number of elements that are in the list after the new node is added.
  • int length(struct node *head) – This function will return the number of nodes in the list. The head node is the first node in the list. If we passed another node, besides the first node of the list, then this function would return the number of nodes from that node to the end of the list.
  • void deletelist(struct node **head) – Deletes the list and frees the memory being used.
  • struct node *searchnode(struct node *head, char *name) – This function will search the list and return the first structure that has a name element equal to the name argument.
  • int removenode(struct node **head, struct node *remove) – This function will search the list for the remove node and remove it from the list. This function will return a 0 if it was successful in finding and removing the node or a -1 if the remove node could not be found.
Now lets look at each of the functions and see how they work. We will start with the struct node *buildnode(int num, char *name) function. This function takes two arguments and build a new node structure with those arguments. Here is the code:

struct node *buildnode(int num, char *name) {
   struct node *new = (struct node *)malloc(sizeof(struct node));
   new->num = num;
   strncpy(new->name, name, sizeof(new->name));
   new->next = NULL;
   return new;
}
This function starts off by allocating memory needed for the new node structure with the malloc() function. We will need to manually release this memory when we are finished with this node otherwise we will have memory leaks in our application.

Next we assign the values to our structure. Notice that we use the strncpy() function to copy the name value into our structure. This is done because the char pointer that was passed to our function may get released or reused, so in order to make sure that we do not lose the value we copy it into the structure. We also set the next pointer to NULL because it is not currently part of the linked list. Remember this function just creates a node but does not put it in a linked list. To put a node into a linked list we we use the addnode() function.

Now we will look at our int addnode(struct node *head, struct node *add) function. This function will add a node to the end of the list and return the total number of nodes after the node is added.

int addnode(struct node *head, struct node *add) {
   struct node* current = head;
   int count = 0;
   while (current->next != NULL) {
      count++;
      current = current->next;
   }
   current->next = add;
   count++;
   return count;
}
The addnode() function accepts two arguments; the first argument is the first node of the list and the second argument is the node to add. In order to add a node to the end of the list, we need to loop though the list to find the end. This is a weakness of singly linked list; since we do not store the end of the list or the number of nodes in the list we need to loop though the whole list to determine the number of nodes or to find the end of the list.

Since we do not want to move the pointer that was passed into the function which points to the first node of the list, we create a new pointer that we name current that also points to the first node of the list. We then set up a while loop that loops through the list until we reach the end of the list. We know that we have found the last node when the next pointer of that node points to NULL rather than another node. If the next pointer does not point to NULL, we increment our counter and move the current point to point to the next node in our list.

Once we find the last node we set the next pointer of that node to point to the node that we are adding to the list. This will put the new node at the end of the list. This does assume that the next pointer within the node that we are adding points to NULL and not another node in the list. If the next pointer in the new node points to another node in the list then we would set up a linked list that loops around in a circle. This would create an endless loop when we attempt to find the end of the list or when we search for a specific node in the list. To be on the safe side we could put a line in the function that sets the next pointer of the new node to NULL but I left that out because this function could also be used to combine two linked lists where the next pointer may point to another node in a separate list.

Next we will look at the int length(struct node *head) function. This function will return the number of nodes in our list. This function accepts one argument which is the first node in the list. Here is the code for the length() function:

int length(struct node *head) {
   struct node* current = head;
   int count = 0;
   while (current != NULL) {
      count++;
      current = current->next;
   }
   return count;
}
The length function is a duplicate of our addnode() function described earlier except that we are not adding a new node to the list once we find the end of the list.

Now lets look at the void deletelist(struct node **head) function. This function will delete the whole list and free the memory that the list uses. This function takes one argument which is a pointer to a pointer that points the the first node of the list to remove. Here is the code for our deletelist() function.

void deletelist(struct node **head) {
    struct node *next;
    struct node *current = *head;
    while (current) {
       next = current->next;
       free(current);
       current=next;
    }
    *head = NULL;
}
In the deletelist() function we loop through the list. For each node in the list we assign the next pointer to point to the next node in the list. We then use the free() function to free the memory that is assigned to the current node. This allows your application to reuse this memory location and prevents memory leaks. We then set the current pointer to point to the next node in the list. Finally, once all of the nodes are removed, we set the pointer which pointed to the first node in the list to NULL to prevent our application from using it by mistake.

Now lets see how the struct node *searchnode(struct node *head, char *name) function works. This functions searches the linked list for the first node that has a name value that is equal to the name argument passed to the function. This function takes two arguments; the first argument is a pointer to the first node in the linked list and the second argument is a pointer to the char string that we are searching for. Lets look at the code for the searchnode() function.

struct node *searchnode(struct node *head, char *name) {
   struct node* current = head;
   while (current != NULL) {
   if (strcmp(current->name,name) == 0)
      return current;
      current = current->next;
   }
   return NULL;
}
We start off by creating a while loop that loops though our list. We then compare the name element of each node with the name argument passed into the function using the strcmp() function. If they are equal, then we found the node we are looking for and return the current node. If they are not equal, we our loop moves to the next node. If we are unable to find a node that contains the name argument we return NULL.

Finally lets look at the int removenode(struct node **head, struct node *remove) function. This function will remove a specified node from our linked list. This function takes two arguments; the first argument being a pointer to a pointer that points to the linked list to search and the second argument being a pointer to the node to remove. The removenode() function will return 0 if the node was found and removed or -1 if the node was not removed. Lets look at the code:

int removenode(struct node **head, struct node *remove) {
   struct node* current = *head;
   struct node* prev = NULL;
   while (current != NULL) {
       if (current == remove) {
          if (prev == NULL)
              *head = current->next;
          else
             prev->next = current->next;
          free(current);
          return 0;
       }
       prev=current;
      current = current->next;
   }
   return -1;
}
We begin the removenode() function by defining two pointers. We set the first pointer, current, to point to the first node of our list and set the second pointer, prev, to point to NULL. When we set up our while loop that will loop though our list, the current pointer will always point to the current node that we are checking and the prev pointer will always point to the previous node. We will need to know the previous node in our list because when we find the node to remove, well will need to change the next pointer of the previous node so it no longer points to the node we wish to remove. Lets look at a diagram that shows how we are going to remove a node from our list.

In the diagram we can see that in order to remove node2 from our list we need to change the next pointer of node1 to point to node3 rather than node2. We would then free the memory allocated to node2 so we do not have memory leaks in our application.

Once we have our two pointers defined we create a while loop that will loop though our list.
If the current node is equal to the remove node then this is the node to remove. If this is the node to remove we check to see if it is the first node in the list by seeing if the prev pointer is pointing to NULL. If this is the first node then we change the head pointer, that was passed into our function, to point to the next node in the list otherwise we set the next pointer from the previous structure to point to the node that the current node's next pointer is pointing too. Finally we free the memory that is used by the current node and return 0 signifying that we found and removed the node.

If the current node is not equal to the remove node then we set the prev pointer to point to the current node and the current pointer to point to the next node in the list. If we loop though the whole list and we do not find the remove node, then we return a -1 signifying that we could not find the node to remove.

Now lets look at some code to test our linked list library:

#include <stdio.h>
#include "linkedlistlib.h"
#include <time.h> 
void waitFor(unsigned int secs) {
    long retTime = time(0) + secs;
    while (time(0) < retTime);
   }
int main()
{
    printf("Hello world\n");
    int i;
    for (i=0; i< 500; i++) {
       struct node *first = buildnode(1,"Jon");
       struct node *second = buildnode(2, "Kim");
       struct node *three = buildnode(3, "Kailey");
       struct node *four = buildnode(4, "Kara");

       addnode(first, second);
       addnode(first, three);
       addnode(first, four); 
       printf("%d)----------\n",i);
       printf("Count %d\n", length(first));
       struct node *found = searchnode(first, "Kailey");
       if (found != NULL)
          printf("found: %d %s\n",found->num, found->name); 
       removenode(&first, first);
       printf("Count after remove %d\n", length(first));
       removenode(&first, found);
       printf("Count after second remove %d\n", length(first)); 
       deletelist(&first);
       printf("found: %d\n",length(first));
       printf("-------------------\n");
       waitFor(2);
    }
    return (0);
}

Inside the main() function, we begin by creating a for loop that will loop 500 times. This loop will allow us to see how our library performs by repeating the various tasks 500 times. If we analyze the memory usage while this runs it will also help us to detect any memory leaks.

Within the for loop we create four nodes using the buildnode() function. We then create our linked list by adding the last three nodes to our list using the addnode() function. Notice that we do not add the first node to the list with the addnode() function, that is because we use that first node as the first node for the list.
Now that we have our list built we verify that the list contains four nodes by using the length() function which returns the number of nodes in our list and print that count to the screen.

Next we use the searchnode() function to search for a node that contains the name “Kailey”. If we find a node that contains “Kailey” then we print the num and name elements of that structure to the screen.

We then try to remove the first node in our list by calling the removenode() function. We verify that the node was removed by printing out the total number of nodes in the list after we called the removenode() function. To verify that we can correctly remove multiple nodes, we then remove the “Kailey” node that we found earlier in this loop and once again print out the number of nodes in the list to the screen.

Finally we delete the list using the deletelist() function and once again print out the number of nodes in the list to verify that they were all removed.

I hope this post helps you understand linked lists a little better.



Thursday, January 9, 2014

TCP/IP Networking Terms

As we dive into network development we will be throwing around a lot of networking terms.  For some, these terms may be new or they may be misunderstood so this post will define a few of the more import terms that you should know.


IP Address:  Every device on an IP (Internet Protocol) network has a unique identifier known as an IP Address.  This address identifies both the host and the location of the device.  Currently there are two versions of the Internet Protocol:

   IPv4:  This is currently the standard for the Internet.  An IPv4 Address looks like this:  74.125.137.191
   IPv6:   This is the next generation of the Internet Protocol.  An IPv6 address looks like this:  2001:0db8:0000:0000:0000:ff00:0042:8329
Subnet:  Is a logical subdivision of devices on an IPv4 Network.  All devices that belong to a subnet have the first few Octets (numbers) in common.  The Netmask will define which IP Address range belongs to a given subnet.

Netmask:  Is a 32-bit mask that is used to specify the IPv4 Address range that belongs to a given subnet.  Below are a few examples that shows a device with an IP Address of 192.168.10.10 and then applies a netmask to that address.  The Last column (IP Address Range) then shows the range of IPv4 Addresses of other devices in the same subnet as the 192.168.10.10 device.






IP Address 
Netmask
Masked Bit
IP Address Range
192.168.10.10
255.255.255.248
29
192.168.10.9 -> 192.168.10.14
192.168.10.10
255.255.255.128
25
192.168.10.1 -> 192.168.10.126
192.168.10.10
255.255.255.0
24
192.168.10.1 -> 192.168.10.254
192.168.10.10
255.255.0.0
16
192.168.0.1 -> 192.168.255.254





Gateway:  Is usually a router that acts as an access point to other networks or subnets.  For example, if device A wants to send a packet to device B however device B is not on device A’s subnet then device A will send the packet too a gateway and rely on that gateway to route the packet to the correct location.  A device should always have one default gateway and may have multiple other gateways to specific subnets.

Fully Qualified Domain name:  A fully Qualified Domain Name (FQDN) is a unique name that can be used to refer to a device on an IP network.  Some examples of a FQDN are http://network-development.blogspot.com or www.apple.com.  We generally use FQDN because, as humans, it is much easier for us to memorize a name then it is for us to memorize a set of numbers like IP Addresses.

DNS Server:  In order for two devices to communicate on an IP network they must know each other’s IP Address.  Therefore if you were to enter http://www.blogspot.com into your web browser the first thing your computer would need to do is to convert the www.blogspot.com name to an IP Address.
A DNS Server will convert a FQDN to an IP Address.  To see this in action, we can open a terminal window and use the nslookup command to perform DNS lookups. 

Port:  While the IP address identifies the device to connect too, the port uniquely identifies the process within the device to connect too.  A device has 65,535 available ports with the first 1023 ports being reserved for common protocols like HTTP, SSH, FTP…

BSD Socket API:  Is part of the POSIX UNIX specifications and offers a set of standard functions used for Inter-process network communications.  We will be discussing sockets a lot in this blog.

Packet:  When devices on a TCP/IP network want to exchange information with each other they encapsulate that information in packets.  We will be talking about packets a lot on this blog.

Byte Order:  The byte order refers to the order that data is stored in memory.  As a human we think of the word ‘dog’ as a ‘d’ followed by a ‘o’ which is followed by a ‘g’.  Some devices store information the same way with the most significant digit first.  Other devices store the information with the least significant digit first where the word ‘dog’ is store ‘g’ followed by ‘o’ followed by ‘d’.  On devices that store the most significant number first it is known as Big-Endian and on devices that store the least significant number first it is knows as Little-Endian.


Network Byte Order:  The byte order that the network sends information.  For Internet Protocol the standard is Big-Endian.  We will be looking at the correct way to convert network byte order to host byte order many times in this blog.

We will be adding additional terms to this glossary as needed.