C++

C++

What is polymorphism

The derived class can be assigned to based class.

What is virtual function

Virtual function can be dynamically bind. The virtual class from the base class can be redefined in derived class

…more(https://github.com/huihut/interview#-cc)

ELF

What does we execute before main

__start -> libc_start_main

What is contain in the first three of got

dyncami, linkmap, and dlruntimeresolve

Utility for each register

r0-r3 用作传入函数参数,传出函数返回值。在子程序调用之间,可以将 r0-r3 用于任何用途。被调用函数在返回之前不必恢复 r0-r3。如果调用函数需要再次使用 r0-r3 的内容,则它必须保留这些内容。 r4-r11 被用来存放函数的局部变量。如果被调用函数使用了这些寄存器,它在返回之前必须恢复这些寄存器的值。 r12 是内部调用暂时寄存器 ip。它在过程链接胶合代码(例如,交互操作胶合代码)中用于此角色。在过程调用之间,可以将它用于任何用途。被调用函数在返回之前不必恢复 r12。 r13 是栈指针 sp。它不能用于任何其它用途。sp 中存放的值在退出被调用函数时必须与进入时的值相同。 r14 是链接寄存器 lr。如果您保存了返回地址,则可以在调用之间将 r14 用于其它用途,程序返回时要恢复 r15 是程序计数器 PC。它不能用于任何其它用途。

8.malloc的具体操作 1) 获取分配区的锁,为了防止多个线程同时访问同一个分配区,在进行分配之前需要 取得分配区域的锁。线程先查看线程私有实例中是否已经存在一个分配区,如果存 在尝试对该分配区加锁,如果加锁成功,使用该分配区分配内存,否则,该线程搜 索分配区循环链表试图获得一个空闲(没有加锁)的分配区。如果所有的分配区都 已经加锁,那么 ptmalloc 会开辟一个新的分配区,把该分配区加入到全局分配区循 环链表和线程的私有实例中并加锁,然后使用该分配区进行分配操作。开辟出来的 新分配区一定为非主分配区,因为主分配区是从父进程那里继承来的。开辟非主分 配区时会调用 mmap()创建一个 sub-heap,并设置好 top chunk。 2) 将用户的请求大小转换为实际需要分配的 chunk 空间大小。 3) 判断所需分配chunk的大小是否满足chunk_size <= max_fast (max_fast 默认为 64B), 如果是的话,则转下一步,否则跳到第 5 步。 3.5) TCache 4) 首先尝试在 fast bins 中取一个所需大小的 chunk 分配给用户。如果可以找到,则分 配结束。否则转到下一步。 5) 判断所需大小是否处在 small bins 中,即判断 chunk_size < 512B 是否成立。如果 chunk 大小处在 small bins 中,则转下一步,否则转到第 6 步。 6) 根据所需分配的 chunk 的大小,找到具体所在的某个 small bin,从该 bin 的尾部摘 取一个恰好满足大小的 chunk。若成功,则分配结束,否则,转到下一步。 7) 到了这一步,说明需要分配的是一块大的内存,或者 small bins 中找不到合适的 chunk。于是,ptmalloc 首先会遍历 fast bins 中的 chunk,将相邻的 chunk 进行合并, 并链接到 unsorted bin 中,然后遍历 unsorted bin 中的 chunk,如果 unsorted bin 只 有一个 chunk,并且这个 chunk 在上次分配时被使用过,并且所需分配的 chunk 大 小属于 small bins,并且 chunk 的大小大于等于需要分配的大小,这种情况下就直 接将该 chunk 进行切割,分配结束,否则将根据 chunk 的空间大小将其放入 small bins 或是 large bins 中,遍历完成后,转入下一步。 8) 到了这一步,说明需要分配的是一块大的内存,或者 small bins 和 unsorted bin 中 都找不到合适的 chunk,并且 fast bins 和 unsorted bin 中所有的 chunk 都清除干净 了。从 large bins 中按照“smallest-first,best-fit”原则,找一个合适的 chunk,从 中划分一块所需大小的 chunk,并将剩下的部分链接回到 bins 中。若操作成功,则 分配结束,否则转到下一步。 9) 如果搜索 fast bins 和 bins 都没有找到合适的 chunk,那么就需要操作 top chunk 来 进行分配了。判断 top chunk 大小是否满足所需 chunk 的大小,如果是,则从 top chunk 中分出一块来。否则转到下一步。 10) 到了这一步,说明 top chunk 也不能满足分配要求,所以,于是就有了两个选择: 如 果是主分配区,调用 sbrk(),增加 top chunk 大小;如果是非主分配区,调用 mmap 来分配一个新的 sub-heap,增加 top chunk 大小;或者使用 mmap()来直接分配。在 这里,需要依靠 chunk 的大小来决定到底使用哪种方法。判断所需分配的 chunk 大小是否大于等于 mmap 分配阈值,如果是的话,则转下一步,调用 mmap 分配, 否则跳到第 12 步,增加 top chunk 的大小。 11) 使用 mmap 系统调用为程序的内存空间映射一块 chunk_size align 4kB 大小的空间。 然后将内存指针返回给用户。 12) 判断是否为第一次调用 malloc,若是主分配区,则需要进行一次初始化工作,分配 21 一块大小为(chunk_size + 128KB) align 4KB 大小的空间作为初始的 heap。若已经初 始化过了,主分配区则调用 sbrk()增加 heap 空间,分主分配区则在 top chunk 中切 割出一个 chunk,使之满足分配需求,并将内存指针返回给用户。

How to map virtual memory to physical memory

We need to get the virtual address to locate the page. Then find offset in physical in Page Table and convert to physical memory

How to implement breakpoint

software breakpoint -> replace original instruction with 0xcc hardware breakpoint -> special register and check PC register

Alignment

To easier locate data, the data need to be aligned as fixed integer

Get pointer

call然后出栈

Compiler Theory

Process from source code to program?

source code -> lexer -> parser -> -> semantic -> interpreter/code generator

Identify the leader of each basic block

  • First instruction
  • Any target of a jump
  • Any instruction immediately following a jump

Dominator

  • Dominator: Node d dominates node n in a graph (d dom n) if every path from the start node to n goes through d
  • Strictly Dom(sdom): d dom n and d != n
  • Dominant frontier: d dom prev(n) and cannot d sdom w
  • D-Tree: A tree that one node directly dominate another

Convert to SSA

SSA

Gather all the defsites of every variable

  • Then, for every variable – foreach defsite
  • foreach node in DominanceFrontier(defsite)
    • if we haven’t put phi() in node, then put one in
    • if this node didn’t define the variable before, then add this node to the defsites

Renaming varaible

According to D-Tree, push to stack and pop accordingly to rename

Loop

– single entry point – edges must form at least a cycle

  • A back edge is an arc whose head dominates its tail

phi-node

At each join point insert phi-node functions for all live variables

Some optimization

  • Constant folding: calculate al constant operations to one constant
  • Loop Invariant Code Motion: move statement from loops to a preheader of the loop to avoid redundant calculation
  • Lazy Code Motion:

Program Analysis

pointer analysis

Anderson: One node for each memory location/Each node contains a points-to set Steensgaard: Union based, thus faster because no need to extract sub-node

Data-Set Analysis

IR

Benefit: eliminate side-effect(e.g. overflow signed will not show explicitly, then possible wrong checking), uniform-platform for less works

Binary Ninja IR phases: LLIR: eliminate side effect, MLIR: has jump table(if else jmp), register/stack are all treated as variable, has type info

Type inference

use library functions, and then use type lattice to group up type. eventually use abstract interpretation and constraint to solve type info