My Vault

mem-org

3 min read

Memory

  • For human memory, see Memory.

Hardware

  • Bus Timing diagram
  • RAM
    • SRAM
    • DRAM
  • ROM
    • EEPROM
    • EPROM
    • Flash
  • MMU

Segments

  • Memory space for a program/process is separated into logical segments.
  • Code, Data, Heap, and Stack
  • “Segmentation Fault” means segments are used improperly.
  • “Each process has an illusion of having all memory in the machine”. Additional pages are allocated when they are needed.
  • break pointer and stack ptr marking the boundary of heap and stack.

mem org

Stack

For data structure, refer to stack. For function call using stack, see Function Call.

  • A guard page is paced around stack, accessing this not yet allocated page triggers page fault and new pages will be allocated for stack.
  • Push and pop of the stack, stack pointer is modified accordingly.

Heap

Fro data structure, refer to heap.

  • Heap is treated as a doubly linked-list of chunks.
  • prog calls malloc, which calls sbrk to request additional page.
  • A struct is used to keep information about chunks in the heap. This struct is paced at the head of each chunk.
  • Calling free(p) is equivalent to p->state = FREE. (change it to free) Adjacent free chunks are also merged.
struct chunk {
    enum {FREE, USED} state;
    int checksum;
    int size;
    struct chunk *next;
    struct chunk *prev;
};

How does Valgrind work?

  • Always request a new page for memory allocated.
  • Also request a page at the front and at the end of the page allocated.
  • Mark these two extra pages as invalid.
  • Thus we get to know which memory reference caused exception.
  • This process is slow and costs a lot more memory.
  • Heap Fragmentation and Garbage Collection. Moving all blocks can only be done in dynamic language with Garbage Collection (since we need to “announce” this change of address to pointers.)
  • Preventing fragmentation? Delay fragmentation by changing the behavior of malloc.
    • First fit
    • Best fit = choose the smallest chunk that fits
    • Worst fit = choose the biggest chunk that fits
    • Next fit = remember last success, and start from there next time. Constructive laziness. It's simple, and doesn't do any thing bad.

Locating Data

  • Global data
    • Referenced by name in assembly language
    • By absolute address - however, the address might be too long
    • By address relative to the data segment
    • By address relative to the PC
  • Local data - as an offset to the current frame pointer
  • Heap data - by the pointer

Loading

  • Executable Formats
    • Binary blob
      • All the segments are dumped into this binary.
      • A lot of spaces are wasted. e.g. a large global array initialized as all 0.
    • a.out Executable Format
      • The first assembler outputs to a.out
      • Header contains a magic number to define executable, and sizes of each segments, as well as entry point.
      • Header → Text → Data → Symbol
    • Extensible Linking Format (ELF), contains a section table, supports dynamically linked libraries.

Graph View