.dp-highlighter { font-family: "Consolas", "Monaco", "Courier New", Courier, monospace; font-size: 12px; background-color: #E7E5DC; width: 99%; overflow: auto; margin: 18px 0 18px 0 !important; padding-top: 1px; /* adds a little border on top when controls are hidden */ } /* clear styles */ .dp-highlighter ol, .dp-highlighter ol li, .dp-highlighter ol li span { margin: 0; padding: 0; border: none; } .dp-highlighter a, .dp-highlighter a:hover { background: none; border: none; padding: 0; margin: 0; } .dp-highlighter .bar { padding-left: 45px; } .dp-highlighter.collapsed .bar, .dp-highlighter.nogutter .bar { padding-left: 0px; } .dp-highlighter ol { list-style: decimal; /* for ie */ background-color: #fff; margin: 0px 0px 1px 45px !important; /* 1px bottom margin seems to fix occasional Firefox scrolling */ padding: 0px; color: #5C5C5C; } .dp-highlighter.nogutter ol, .dp-highlighter.nogutter ol li { list-style: none !important; margin-left: 0px !important; } .dp-highlighter ol li, .dp-highlighter .columns div { list-style: decimal-leading-zero; /* better look for others, override cascade from OL */ list-style-position: outside !important; border-left: 3px solid #6CE26C; background-color: #F8F8F8; color: #5C5C5C; padding: 0 3px 0 10px !important; margin: 0 !important; line-height: 14px; } .dp-highlighter.nogutter ol li, .dp-highlighter.nogutter .columns div { border: 0; } .dp-highlighter .columns { background-color: #F8F8F8; color: gray; overflow: hidden; width: 100%; } .dp-highlighter .columns div { padding-bottom: 5px; } .dp-highlighter ol li.alt { background-color: #FFF; color: inherit; } .dp-highlighter ol li span { color: black; background-color: inherit; } /* Adjust some properties when collapsed */ .dp-highlighter.collapsed ol { margin: 0px; } .dp-highlighter.collapsed ol li { display: none; } /* Additional modifications when in print-view */ .dp-highlighter.printing { border: none; } .dp-highlighter.printing .tools { display: none !important; } .dp-highlighter.printing li { display: list-item !important; } /* Styles for the tools */ .dp-highlighter .tools { padding: 3px 8px 3px 10px; font: 9px Verdana, Geneva, Arial, Helvetica, sans-serif; color: silver; background-color: #f8f8f8; padding-bottom: 10px; border-left: 3px solid #6CE26C; } .dp-highlighter.nogutter .tools { border-left: 0; } .dp-highlighter.collapsed .tools { border-bottom: 0; } .dp-highlighter .tools a { font-size: 9px; color: #a0a0a0; background-color: inherit; text-decoration: none; margin-right: 10px; } .dp-highlighter .tools a:hover { color: red; background-color: inherit; text-decoration: underline; } /* About dialog styles */ .dp-about { background-color: #fff; color: #333; margin: 0px; padding: 0px; } .dp-about table { width: 100%; height: 100%; font-size: 11px; font-family: Tahoma, Verdana, Arial, sans-serif !important; } .dp-about td { padding: 10px; vertical-align: top; } .dp-about .copy { border-bottom: 1px solid #ACA899; height: 95%; } .dp-about .title { color: red; background-color: inherit; font-weight: bold; } .dp-about .para { margin: 0 0 4px 0; } .dp-about .footer { background-color: #ECEADB; color: #333; border-top: 1px solid #fff; text-align: right; } .dp-about .close { font-size: 11px; font-family: Tahoma, Verdana, Arial, sans-serif !important; background-color: #ECEADB; color: #333; width: 60px; height: 22px; } /* Language specific styles */ .dp-highlighter .comment, .dp-highlighter .comments { color: #008200; background-color: inherit; } .dp-highlighter .string { color: blue; background-color: inherit; } .dp-highlighter .keyword { color: #069; font-weight: bold; background-color: inherit; } .dp-highlighter .preprocessor { color: gray; background-color: inherit; }

Wednesday, December 26, 2007

OS/Architecture notes...

1- What is a segmentation fault, and how does it occur?


First, a word about memory protection. Modern operating systems provide the means to control access to the memory system. A user process should not be allowed to modify its read-only text section. It should not be allowed to read or modify any of the code and data structures in the kernel. It should not be allowed to read or write the private memory of other processes. And it should not be allowed to modify any virtual pages that are shared with other processes unless all parties explicitly allow it (via calls to explicit interprocess communication system calls). Each process usually has its own private virtual memory space, which translates to disjoint or safely shareable physical memory pages.

Remember that in virtual memory systems, we have a Page Table, which contains Page Table Entries (PTEs). A page table entry contains the base address of a physical page in DRAM, or an allocated page on the desk.

Enough of Virtual Memory. The operating system adds three permission bits to PTE entries, called SUP (supervisor), Read, Write bits, and they correspond to root, read, and write privliges respectively. If during the address translation the calling process violates any of those priviliges, it'll generate a protection fault (i.e., segmentation fault)....

Take this example

int main()
{
char* p;
char c;

p = (char*) 0;
c = *p; //generates seg fault
--(1)

}

The line at (1) generates a seg fault because it is trying to read location zero, and when the OS checks, it can't find a page allocated at location 0, and generates a segmentation fault.

p.s. This was a really crude descrition, so don't rely on it completely.... Should allow you to google it better, at the very least.

2- How do you detect if an overflow happened in adding two unsigned integers?

If the result is less than any of the operands, an overflow has occured in the case of unsigned addition. If both x and y less than 2^w (where w is the number of bits, we have no overflow). But s = x + y ==> s >= x (or y). So if s is less than x, or s is less than y, then we have an overflow. This is because in case of an overflow, s = x + y - 2^w (wraps around). THis is because we had a carry on of one, which we can't store, so we decrement the sum by 2^w. And since y < 2^w, y - 2^w < 0, which means s < x, hence overflow occured.

3- I get a stack overflow error at run time, but I can't spot any large stack allocations?

C++ allows you to delcare variables anywhere in the code (almost), unlike C which only allows you to delcare variables at the beginning of a block of instructions. So check large array allocations in the middle of your function/block. For example:


void myFunction(int
iTinyFourByteInteger)
{
int tinyInt1;
int tinyInt2;

int tinyInt3;
....
....
....
//after tens of lines of code
int largeArray[65536];

}

What the compiler did was to inspect your code first, push all local variables on the stack, regardless of where they were declared, then start the executing the first instruction in the function. If you're stepping through a debugger, you won't be able to spot the problem because it'll crash at the opening brace.

Sunday, December 23, 2007

Networking Interview Questions Cont.

These are some of the commonly asked, and not very well answered, questions:

What are the main differences between TCP/UDP?

  • UDP has no connection establishment. TCP has three way handshaking (send SYN, receive SYN-ACK, send ACK), while UDP has no connection establishment, hence called connectionless transport protocol
  • TCP keeps Connection state at the end systems, UDP doesn't. The This connection state includes receive and send buffers, congestion control parameters, and sequence and acknowledgment number parameters.
  • TCP has a 20-byte segment header overhead, while UDP has 8 segment header overhead.
  • TCP has a regulated send-rate. TCP has a congestion control mechanism that throttles the sender when one or more links between sender and receiver becomes excessively congested. This throttling can have a severe impact on real-time applications, which can tolerate some packet loss but require a minimum send rate. On the other hand, the speed at which UDP sends data is only constrained by the rate at which the application generates data, the capabilities of the source (CPU, clock rate, etc.) and the access bandwidth to the Internet.

2- What is Connected UDP?

Usually when creating a UDP socket we say:

socket = socket(PF_INET, SOCK_DGRAM, 0); //socket(family, type, proto)

Then to send using this socket we use:

ssize_t sendto(sock_fd,
void* buf, size_t nBytes,
int flags,
const struct sockaddr* to,
socklen_t len); //ssize_t is how much data the OS accepted to send.

If we use a udp socket in a call to connect, we create what is called connected UDP. This simply tells the OS the address of the peer; no handshaking is necessary and no data is sent to establish that the peer exist (i.e., no data is sent as a result of calling connect() on a udp socket. Why use it? If we communicating with a single peer, this might be useful since:

  1. We can call sendto() with null destination address
  2. We can use write() and send()
  3. We can use read() and recv(), which will return only data from the remote peer we connect()ed to.