ELF format

What are different sections in elf format?
.text, .data, .bss .symbol table .relocation table
Executable code is always placed in a section known as .text; all data variables initialized by the user are placed in a section known as .data; and uninitialized data is placed in a section known as .bss


Why do you need to divide into different sections?
On modern machine architectures, the memory manager can mark portions of memory read-only, such that any attempt to modify a read-only memory location results in the program dying and dumping core. Thus, instead of merely saying that we do not expect a particular memory location to change, we can specify that any attempt to modify a read-only memory location is a fatal error indicating a bug in the application. That being said, typically you cannot individually set the read-only status for each byte of memory—instead you can individually set the protections of regions of memory known as pages. On the i386 architecture the page size is 4096 bytes—thus you could indicate that addresses 0-4095 are read-only, and bytes 4096 and up are writable, for example.

Given that we want all executable portions of an executable in read-only memory and all modifiable locations of memory (such as variables) in writable memory, it turns out to be most efficient to group all of the executable portions of an executable into one section of memory (the .text section), and all modifiable data areas together into another area of memory (henceforth known as the .data section).

* The Data area contains global and static variables used by the program that are not initialized to zero. This segment can be further classified into initialized read-only area and initialized read-write area. For instance the string defined by char s[] = "hello world"; in C and a C statement like int debug=1; outside the main would be stored in initialized read-write area. And a C statement like char *string = "hello world"; makes the string literal "hello world" to be stored in initialized read-only area and the character pointer variable string in initialized read-write area.
* The BSS segment also known as Uninitialized data starts at the end of the data segment and contains all global and static variables that are initialized to zero by default. For instance a variable declared static int i; would be contained in the BSS segment.
* The heap area begins at the end of the BSS segment and grows to larger addresses from there. The Heap area is managed by malloc, realloc, and free, which may use the brk and sbrk system calls to adjust its size (although, note that the use of brk/sbrk and a single "heap area" is not required to fulfil the contract of malloc/realloc/free; they may also be implemented using mmap to reserve potentially non-contiguous regions of virtual memory into the process' virtual address space). The Heap area is shared by all shared libraries and dynamically loaded modules in a process.
* The stack is a LIFO structure, typically located in the higher parts of memory. It usually "grows down" with every register, immediate value or stack frame being added to it. A stack frame consists at minimum of a return address.


Is there any size difference when you initialize a global variable?
Yes. That gets stored in .data section.

What is a symbol table?
symbols are program entry points, variable addresses etc.,
In a.out format we can strip entire symbol table while for .elf some symbols are required to load and run the executable.

what is relocation table?
Relocation table contains references to external functions like printf where to link in text area and operands etc.,

what is static and dynamic linking of libraries?
In the linking stage, the external library functions are resolved and are made part of executable. Its called statically linking while in dynamic linking, the linker notes the fact that the function is called from external file and while initializing, the binary would request for required libraries. So, the binary size is less.

Find out a loop in a singly-linked list

Duplicates In An Array

Given an array of say 1 Billion entries and its is filled with numbers ranging from 1 to 1 Billion
and there can be duplicates of the same number, given a number(between 1 and 1 Billion), whats
the easiest method to find whether the entry is a duplicate in the array.