Bookmarks – Programming

  1. Find k largest elements in a file. https://www.geeksforgeeks.org/?p=2392
  2. Find k  most frequent words in a file. https://www.geeksforgeeks.org/find-the-k-most-frequent-words-from-a-file/
  3. Merge two BSTs. https://www.geeksforgeeks.org/merge-two-balanced-binary-search-trees/
  4. Lowest common ancestor in BST: https://www.geeksforgeeks.org/lowest-common-ancestor-in-a-binary-search-tree/

C – MACROS – Q&A

1.  Write a macro to compare 2 addresses

#define IP_COMP(a,b)\

memcmp((char*)a, (char*)b, sizeof(addr))

2. Write a macro to find the minimum of two values

#define MIN(a,b) ((x)<(y)?(x):(y))

3. Write a macro to have a function similar to sizeof with a variable passed.

#define my_sizeof(var) (char *)(&var+1)-(char*)(&var)

However the above will work only for sizeof(a) where say a is an integer. What about sizeof(int)?

#define my_sizeof(var) \

({ \

__typeof(var) x; \

(char *) (&x+1) – (char*) (&x); \

})

OR

#define SIZEOF(e) ({ typeof(e) x; (void *)(&x+1) – (void *)(&x); })

4. Write a macro to  implement offsetof.

typedef struct bundle_{

int roll;

int thread;

}bundle;

To find the offset of thread, we would write offsetof(bundle, thread)

Now, a macro to this will be :

#define MY_OFFSETOF(x,y) (   (size_t)       &(   (   (x*)0   )->y)     )

 

So our call of MY_OFFSET(bundle, thread) would expand to:

#define MY_OFFSETOF(bundle, thread) (    (unsigned int)     &(((bundle*)0)->thread)         )

 

5. How to make PRINT(x) print x.

https://www.geeksforgeeks.org/write-a-c-macro-printx-which-prints-x/

 

6.  Implement CRASH using macro

https://www.geeksforgeeks.org/crash-macro-interpretation/

There is this snippet

#define CRASH() do { \
      ((void(*)())0)(); \
   } while(false)

((void(*)())0)     ();  >> looks like calling a func().

((void(*)())0) >> Now this is func.

(void(*)())0 >> Now this is func as well

0 is casted to (void(*)()). 

Or rather 0 is casted to void(*)()

As we know, void (*) refers to function and its parameters are nothing, so ()

So what we do is just cast 0 to function pointer which takes no parameters and call it with ().

—————-

Another way to explain this is below.

Want to call a function that is no where – that is in a memory that has no pages and is invalid. 0 is one such memory that is mapped.

So we should be doing 0(). However we would need to cast 0 to a function pointer to make it explicit.

(function prototype)0()

our function prototype would be -> void (*) (void) which is also void (*) ()

So it finally this -> ((void(*)()))0()

7.  Write a variable length macro – like printf.

https://www.geeksforgeeks.org/variable-length-arguments-for-macros/

8. Implement MACRO function for htons/ntohs/htonl/ntohl for both BIG ENDIEN and LITTLE ENDIEN machines.

#if BYTE_ORDER == BIG_ENDIAN

#define htons(n) (n)
#define htonl(n) (n)
#define ntohs(n) (n)
#define ntohl(n) (n)

#else

#define htons(n) ((n & 0xFF) << 8) | (n & 0xFF00) >> 8))
#define ntohs(n) htons(n)
#define htonl(n) ((n & 0xFF) << 24) | (n & 0xFF00) << 8) | n & 0xFF000000) >> 24) | n & 0x00FF0000) >> 8) )
#define ntohl(n) htonl(n)

#endif

 

 

 

 

 

 

 

 

 

 

 

C – good to know bits

#define MAX 10

CASE 1: The above needs to be now changes such that – for condition 1 its 10 and for the rest its 20.

You would do the below.

#if defined CONDITION_1

#define MAX 10

#else

#define MAX 20

#endif

The above code would be in a .h file.

 

CASE 2:

Now say the MAX variable is supposed to come at run time. That is you need to call isCondition1() to know if it is really condition 1 in order to proceed.

#define MAX myMax()
static inline int myMax() {
return (isCondition1() ? 10 : 20 );
}

The above code would be in .h file.

Now, a call to MAX will indirectly call the function. This will make implementation clean. As you need not modify .c files with messy call to function isCondition1().

All changes are done in .h file. This is clean.

CASE 3:

What if the above macro MAX is used as a array size? The compiler would complain “variable modified file scope” -> because an array size cannot be a static or const or any such variable. It accepts just #define and absolute values. This would call for dynamic allocation with MAX. The CASE 2 would work good that way.

CASE 4:

The worst case is to add code like the below when CASE 3 is not possible. CASE 3 is not possible incase there is a shared memory and you cannot have dynamic memory allocation. Such cases, go with changing .c file to minimum. How array size cannot be dynamic. Rest of the calls to MAX can change to myMax().

static inline int myMax() {
return (isCondition1() ? 10 : 20 );
}

 

 

 

 

 

 

ICMPv6 RFC

Unlike 8 types in ICMPv4, there are 4 types here.

1. Type =1 DESTINATION UNREACHABLE

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |     Type      |     Code      |          Checksum             |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                             Unused                            |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                    As much of invoking packet                 |
      +                as possible without the ICMPv6 packet          +
      |                exceeding the minimum IPv6 MTU [IPv6]          |
   Code           0 - No route to destination
                  1 - Communication with destination
                        administratively prohibited
                  2 - Beyond scope of source address
                  3 - Address unreachable
                  4 - Port unreachable
                  5 - Source address failed ingress/egress policy
                  6 - Reject route to destination

0 can happen when there is no route including a default route.

1 can happen where there is firewall filter to block this dest address

2 can happen when packet has link local source and global destination address because of which packet should leave the current scope.

3 can happen due to inability resolve the destination address to link

what does below mean?

One specific case in which a Destination Unreachable message is sent
   with a code 3 is in response to a packet received by a router from a
   point-to-point link, destined to an address within a subnet assigned
   to that same link (other than one of the receiving router's own
   addresses).  In such a case, the packet MUST NOT be forwarded back
   onto the arrival link.

4 can happen when transport protocol for example UDP has no listener.

5 can happen when there are ingress and egress policies to reject installed for the source address

6 can happen when there are policies for destination address, to reject.

5 and 6 are subsets of 1

 

2. Type = 2 PACKET TOO BIG

      0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |     Type      |     Code      |          Checksum             |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                             MTU                               |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                    As much of invoking packet                 |
      +               as possible without the ICMPv6 packet           +
      |               exceeding the minimum IPv6 MTU [IPv6]           |

This message is sent when the packet is bigger than what MTU can permit.

3. Type = 3 TIME EXCEEDED MESSAGE

 

       0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |     Type      |     Code      |          Checksum             |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                             Unused                            |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                    As much of invoking packet                 |
      +               as possible without the ICMPv6 packet           +
      |               exceeding the minimum IPv6 MTU [IPv6]           |
   Code           0 - Hop limit exceeded in transit
                  1 - Fragment reassembly time exceeded

4. Type = 4 PARAMETER PROBLEM

 0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |     Type      |     Code      |          Checksum             |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                            Pointer                            |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                    As much of invoking packet                 |
      +               as possible without the ICMPv6 packet           +
      |               exceeding the minimum IPv6 MTU [IPv6]           |
   Code           0 - Erroneous header field encountered
                  1 - Unrecognized Next Header type encountered
                  2 - Unrecognized IPv6 option encountered

5. Type = 128/129 ECHO REQUEST/REPLY

 0                   1                   2                   3
       0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |     Type      |     Code      |          Checksum             |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |           Identifier          |        Sequence Number        |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |     Data ...
      +-+-+-+-+-

The fields are same as IPv4

ICMPv4 RFC

Quick review of ICMP RFC. 8 types.

  1. Type = 3 DESTINATION UNREACHABLE
       0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |     Type      |     Code      |          Checksum             |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                             unused                            |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |      Internet Header + 64 bits of Original Data Datagram      |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

    0 – net unreachable  1 – host unreachable 2 – protocol unreachable 3 – port unreachable 4 – fragmentation needed and DF set 5 – source route failed.                 Note that 2 and 3 are sent by hosts. 4 and 5 are sent by gateways

  2. Type = 11 TIME EXCEEDED
        0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |     Type      |     Code      |          Checksum             |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                             unused                            |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |      Internet Header + 64 bits of Original Data Datagram      |

    0 – Time to live exceeded in transit (gateway)  1 – Fragment reassembly time exceeded (host)

  3. Type = 12 PARAMETER PROBLEM code = 0 (pointer indicates error)
        0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |     Type      |     Code      |          Checksum             |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |    Pointer    |                   unused                      |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |      Internet Header + 64 bits of Original Data Datagram      |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

64 bits of original data datagram is for the receiver to identify the process to handover this packet to.

4. Type = 4 SOURCE QUENCH MESSAGE

If sender is sending too fast, the receiver is not able to process and Q gets gull, it would send back this message to ask the source to cut down on the rate.

5. Type 5 REDIRECT MESSAGE

 0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     Type      |     Code      |          Checksum             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                 Gateway Internet Address                      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |      Internet Header + 64 bits of Original Data Datagram      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Code 0 -> Redirect datagram for the network

Code 1 -> Redirect datagram for the host

Code 2 -> Redirect datagram for TOS & network

Code 3 -> Redirect datagram for TOS & Host

Router or gateway G1 checks its router table. If destination address can be reached with G2 on a shorter path, it(G1) sends a redirect message to host. Host can sent packets to G2.

6. Type = 8/0 ECHO REQUEST/ECHO REPLY

 0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     Type      |     Code      |          Checksum             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |           Identifier          |        Sequence Number        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     Data ...
   +-+-+-+-+-

 Sequence number is used to number the repeats. Identified is used to identify the session like how port numbers are used for TCP/UCP sessions.

7.Type = 13/14 TIMESTAMP REQUEST/REPLY MESSAGE

0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     Type      |      Code     |          Checksum             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |           Identifier          |        Sequence Number        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     Originate Timestamp                                       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     Receive Timestamp                                         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     Transmit Timestamp                                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

 

Timestamps are 32 buts values in milliseconds. Originate = t1; Receive = t2; Transit = t3;

t2 is recorded when receiver first touched the packet. t3 is recorded when echoer touched before sending the packet back to source.

t3 – t2 = processing time at receiver.

8. Type = 15/16 INFORMATION REQ/REP

 0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     Type      |      Code     |          Checksum             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |           Identifier          |        Sequence Number        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

I don’t understand what below means.

This message is a way for a host to
      find out the number of the network it is on.

 

 

 

 

Memory Leaks

Memory Leaks:

Memory leaks are common in systems and there are many ways to narrow down source of leaks.

Here I would discuss various ways to approach memory leaks.

There are two kinds. One is the case where there is reference still alive and memory in heap is already gone. The other when there is no reference and the memory is stuck in heap. A lot of memory tools today use mark and sweep method that actually checks the heap for allocated addresses not present in data segment to identify leaks. So this boils down to – no reference case, where in there is just the heap allocated for the memory without the reference. However the other case where there is a reference is still hanging around (due to design/coding error) causing the such tools to not work.

The ways we could find leaks are the following:

1. Use valgrind if it is possible to bring it in. There are cases where it would be difficult to bring in valgrind.

2. Use mtrace.

Refer to https://munir.wordpress.com/2006/08/05/finding-memory-leaks-using-mtrace/

You need to add mtrace() at the start and muntrace() at the end after including mcheck.h

Once this is done, use MALLOC_TRACE=mtrace.log during compilation. Further to parse the log file better use mtrace perl utility and this will give the leaks with line numbers in code.

3. Use backtrace function and backtrace_symbols function by including execinfo.h. Dump the trace in a file. Write a python script to analyse the output and print out the source of leak.

http://man7.org/linux/man-pages/man3/backtrace_symbols.3.html

The above link is a man page for backtrace. The link also has sample code.

I have tried this out along with a python script to parse the final output.

4. The below journal mentions about dmalloc and mcheck

http://www.linuxjournal.com/article/6059?page=0,1

5. Hooks for malloc

http://www.gnu.org/software/libc/manual/html_node/Hooks-for-Malloc.html

and

consistency checking with

http://www.gnu.org/software/libc/manual/html_node/Heap-Consistency-Checking.html#Heap-Consistency-Checking