[Patch 0/5][Djprobe]Djprobe Coexist with Kprobes

[Masami Hiramatsu <hiramatu at sdl dot hitachi dot co dot jp>]

Hi,

I developed patches of djprobe for coexistance with kprobes.
It includes a multiprobe support patch by using rcupdate.
I also wrote a Q&A document about djprobe and attach to this mail.

Best Regards,

-- 
Masami HIRAMATSU
2nd Research Dept.
Hitachi, Ltd., Systems Development Laboratory
E-mail: hiramatu@sdl.hitachi.co.jp



Direct Jump Probe Q&A

Author: Masami Hiramatsu <hiramatu@sdl.hitachi.co.jp>
Date: 29, Sep., 2005

Q: What is the Direct Jump Probe (Djprobe)?
A: Djprobe is a low overhead probe method for linux kernel. 

Q: What is different from Kprobes?
A: The most different feature is that the djprobe uses a jump instruction code instead of 
breakpoint instruction code. It can reduce overheads of probing especially when the 
probes are executed frequently.

Q: How does the djprobe work?
A: First, Djprobe copies some instructions modified by a jump instruction into the 
middle of a stub code buffer. Next, it overwrites the instructions with the jump 
instruction whose destination is the top of that stub code buffer. In the top of the stub 
code buffer, there is a call instruction which calls a probe function. And, in the bottom of 
the stub code buffer, there is a jump instruction whose destination is the next of the 
modified instructions. 
 On the other hand, Kprobe copies only one instruction which will be modified by 
breakpoint instruction, and overwrites it breakpoint instruction. When breakpoint 
interruption handling, it executes the copied instruction with the trap flag. When trap 
interruption handling, it corrects IP(*) for returning to the kernel code.
 So, djprobe's work sequence is "jump", "probe", "execute copies" and "jump", whereas 
kprobes' sequence is "break", "probe", "execute copies", and "trap".

(*)Instruction Pointer

Q: Does the djprobe need to modify kernel source code?
A: No. The djprobe is one of the dynamic probes. It can be inserted into running kernel.

Q: Where can the djprobe be inserted in?
A: Djprobe can be inserted in almost all kernel code including the head of almost kernel 
functions. The insertion area must satisfy the assumptions described below. 
(In i386 architecture)
         Insertion Address
         | 
[-2][-1][0][1][2][3][4][5][6][7]
        [ins1][ins2][  ins3 ]
        [<-     DCR       ->]
           [<- JTPR ->]

ins1: 1st Instruction
ins2: 2nd Instruction
ins3: 3rd Instruction
DCR (Detoured Code Region): The area which is including the instructions whose first 
byte is in the range in 5 bytes (this size is from the size of jump instruction) from the 
insertion address. These instructions are copied into the middle of a stub code buffer.
JTPR (Jump Target Prohibition Region): The area which is including the codes among 
codes rewritten in the jump instruction by djprobe except the first one byte.

Assumptions:
i) The insertion address points the first byte of an instruction.
  This is for avoidance of a bad instruction exception.
ii) There are no instructions which refer IP (ex. relative jmp) in DCR.
  EIP has been changed when copied instruction is executed.
iii) There are no instructions which occur context-switch (ex. call schedule()) in DCR.
  If a context-switch occurs in DCR, the next address of an instruction (ex. the address 
of "ins2") is stored in the call stack of previous thread. After that, djprobe overwrites the 
instruction with jump instruction. When the previous thread switches back, it resumes 
execution from the stored address. So it will cause a bad instruction exception.
iv) Destination address of jump or call is not included in JTPR.
  This is for avoidance of a bad instruction exception too.

Q: Should the jump instruction be with in a page boundary to avoid access violation and 
page fault?
A: No. The x86 processors can handle non-aligned instructions correctly. We can see 
many non-aligned instructions in the kernel binary. And, in the kernel space, there is no 
page fault. Kernel code pages are always mapped to the kernel page table. 
So it is not necessary to care of page boundaries in x86 architecture.


Q: How does the djprobe resolve problems about self/cross-modifying code? In Pentium 
Series, Unsynchronized cross-modifying code operations except the first byte of an 
instruction can cause unexpected instruction execution results.
A: Djprobe uses a trick code to resolve the problems. It modifies the instructions as 
following.
1) Register special handler as a kprobe handler. (And a break point instruction is 
written on the first byte of the insertion address by kprobes.)
2) Check safety (this is described in the next question's answer).
3) Write only the destination address part of jump instruction on the kernel code. (This 
operation is not synchronized)
4) Call "cpuid" on each processor for synchronization.
5) Write the first byte of the jump instruction. (This operation is synchronized 
automatically)

Q: How does the djprobe guarantee no threads and no processors are executing the 
modifying area? The IP of that area may be stored in the stack memory of those threads.
A: There are three problems:
 i) Problem caused by the multi processor system
  Another processor may be executing the area which is overwritten by jump 
instruction. Djprobe should guarantee no processor is executing those instructions when 
modify it.
 ii) Problem caused by the interruption
  An interruption might have occurred in the area which is going to be overwritten by 
jump instruction. Djprobe should guarantee all interruptions which occurred in the area 
have finished.
 iii) Problem caused by full preempt kernel
  In case of Problem (iii), it is described in the next question's answer. 

The Djprobe uses the workqueue to resolve Problem (i) and (ii).
1) Copy the entire of the DCR (described above) into the middle of a stub code buffer.
2) Register special handler as a kprobe handler. This special handler changes kprobe's 
resume point to the stub code buffer. 
3) Clear the safety flags of all processors.
4) Register a safety checking work to the workqueue on each processor.
5) When keventd thread is scheduled on a processor, it executes the work. In this time, 
this processor is not executing the area which is overwritten by jump instruction. And 
also it has finished all interruptions. Because, in the case of voluntary preemption or 
non preemption kernel, the context switch does not occur in the extension of 
interruption. 
6) The work sets safety flag of this processor and checks whether all the flags were set. 
If all flags were set, it writes the jump instruction.

Q: Can the djprobe work with kernel full preemption?
A: No, but you can use the djprobe's interface. When kernel full preemption is enabled, 
we can't ensure that no threads are executing the modified area. It may be stored in the 
stack of the threads. In this case, the djprobe interfaces are emulated by using kprobe.
 The latest linux kernel supports not only full preemption but also the voluntarily 
preemption. In the case of voluntarily preemption, threads are scheduled from only 
limited addresses. So it is easy to check that the preemption can not occur in the 
modified area.

Q: Can several djprobes be inserted in the same address?
A: Yes. Several djprobes which are inserted in the same address are aggregated and 
shares one instance. 
NOTE: When a new djprobe's insertion address is in another djprobe's JTPR (above 
described), or the another djprobe's insertion address is in the new djprobe's JTPR, 
register_djprobe() fails to register the new djprobe and returns -EEXIST error code.

Q: Can djprobe be used with kprobes in same address?
A: Yes, djprobe can coexist with kprobes. When a kprobe is inserted in the address in 
where a djprobe was already inserted, the djprobe removes a jump code and inserts a 
breakpoint (and it is driven by kprobes). When a djprobe is inserted in the address in 
where a kprobe was already inserted, the djprobe behaves like a kprobe.
After all kprobes are removed from the address, the djprobe inserts a jump code again.