Watch Point

The function of watchpoints is to monitor when the value of an expression changes. If you've never used watchpoints before, try them out in GDB.

Extending the functionality of expression evaluation

You've already implemented arithmetic expressions, but these expressions are composed of constants and their values don't change. Such expressions do not make sense in a watchpoint, so in order to utilize the watchpoint's functionality, you first need to extend the expression evaluation functionality.

We use BNF to illustrate what functionality needs to be extended:

<expr> ::= <decimal-number>
  | <hexadecimal-number>    # Start with "0x"
  | <reg_name>              # Start with "$"
  | "(" <expr> ")"
  | <expr> "+" <expr>
  | <expr> "-" <expr>
  | <expr> "*" <expr>
  | <expr> "/" <expr>
  | <expr> "==" <expr>
  | <expr> "!=" <expr>
  | <expr> "&&" <expr>
  | "*" <expr>              # pointer dereference

Their function is the same as their corresponding C operators, including precedence and combinability, so if in doubt, consult the documentation.

Regarding getting the value of a register, this is obviously an ISA-related function. The framework code has prepared the following API.

// nemu/src/isa/$ISA/reg.c
word_t isa_reg_str2val(const char *s, bool *success);

It is used to return the value of the register named s and set success to indicate success.

It is also important to note that how pointer dereferences operator is parsed, and there is no way to distinguish multiplication from pointer dereferences by just looking at the operator itself, because they are both *. We need to distinguish them before recursively evaluating them, otherwise if we treat pointer dereferences as multiplications, the evaluation process will consider the expression to be illegal. It's not that hard to tell them apart, given an expression, you can tell them from each other. In fact, by looking at the type of the token before the *, we can decide whether the * is a multiplication or a pointer dereference, don't you think? Here's the framework for the expr() function.

if (!make_token(e)) {
  *success = false;
  return 0;
}

/* TODO: Implement code to evaluate the expression. */

for (i = 0; i < nr_token; i ++) {
  if (tokens[i].type == '*' && (i == 0 || tokens[i - 1].type == certain type) ) {
    tokens[i].type = DEREF;
  }
}

return eval(?, ?);

The certain type is up to you to figure out! In fact, the above framework can also handle negative numbers, so if you've implemented negative numbers before, you shouldn't have any trouble identifying *.

In addition, we've simplified the expressions in the simple debugger compared to the expressions in GDB, which are not type-specific, so we need to make two extra points:

All results are of type uint32_t.
Pointers also have no type, and for pointer dereferencing, we always read an integer of type uint32_t from the client computer's memory.

Extending the functionality of expression evaluation

You need to implement the functions listed in the above BNF. The above BNF does not list all the operators in C, such as the various bitwise operations, <=, and etc. == and && are likely to be used when using watchpoints, so you are required to implement them. If in the future you find it inconvenient to use a particular operator because it is missing, you can consider implementing it then.

Expression evaluation in riscv64

Since riscv64 is a 64-bit ISA, you need to interpret the result of the expression as a uint64_t type.

Limitation of testing

We have previously implemented an expression generator, but after adding register usage and pointer dereferencing to expression evaluation, the expression generator does not meet all of our needs. This is because the semantics of registers do not exist in C programs, and the semantics of pointer dereferencing are very different from NEMU.

The point here is that testing has its limitations, and no single technique can solve all problems all at once. This is especially true of cutting-edge research: they often solve only a small part of the problem. However, this expression generator gives you a lot of confidence that there is value in thinking about how to easily test your code, even if it is only partially tested.

implement watchpoints

The simple debugger allows the user to set multiple watchpoints and delete watchpoints, so it is better to organize the information of watchpoints in a linked list. The structure of the watchpoint is already defined in the framework code (in nemu/src/monitor/sdb/watchpoint.c).

typedef struct watchpoint {
  int NO;
  struct watchpoint *next;

  /* TODO: Add more members if necessary */

} WP;

However, there are only two members defined in the structure: NO for the watchpoint's ID, and there is no need to explain next . In order to implement the watchpoint feature, you need to add the necessary members to the structure according to your understanding of how watchpoints work. We also use a "pool" data structure to manage the watchpoint object, a part of which is given in the framework code.

static WP wp_pool[NR_WP] = {};
static WP *head = NULL, *free_ = NULL;

The code defines a watchpoint pool, wp_pool, and two linked lists, head and free_, where head is used to organize watchpoints in use and free_ is used to organize free watchpoints, and the init_wp_pool() function will initialize the two linked lists.

Implement watchpoint pool management logic

In order to use the watchpoint pool, you need to write the following two functions (you can modify the parameters and return values of the functions according to your needs).

WP* new_wp();
void free_wp(WP *wp);

The functions new_wp() return a free watchpoint object from the free_ list, and free_wp() puts wp back into the free_ list, these two functions will be used as the interface to the watchpoint pool by other functions. Note that when calling new_wp() there may be no free watchpoint structure, for simplicity you can terminate the program immediately with assert(0). The framework code defines 32 watchpoint objects, which should be enough for general use. If you need more, you can change the value of the NR_WP macro.

These two functions need to perform some linked list insertion and deletion operations, for students who are not familiar with the operation of the linked list, this can be used as an exercise for the linked list.

Recall the past to understand the future

The framework code uses the keyword static when defining variables such as wp_pool, what does static mean in this context? Why is it used here?

Once you have implemented the management logic of the watchpoint pool, you can think about how to implement the watchpoint feature. Specifically, you need to implement the following functionality.

When the user gives an expression to be watched, you need to request a free watchpoint structure via new_wp() and record the expression. All watchpoints are then checked in a loop at the end of the trace_and_difftest() function (defined in nemu/src/cpu/cpu-exec.c), which is called every time the cpu_exec() loop finishes executing an instruction. During the check of the watchpoints, you need to evaluate the corresponding expressions of the watchpoints (you have already implemented the expression evaluation function) and compare their values to see if they have changed, if they have changed, the program will pause due to the triggering of the watchpoints. You need to set the nemu_state.state variable to NEMU_STOP to pause the execution. Finally, you output a message that the user has triggered a watchpoint, and return to the sdb_mainloop() loop to wait for the user's command.
Use the info w command to print information about the watchpoints in use. You can refer to the info watchpoints results in GDB for more information on what to print.
Use the d command to delete watchpoints, you just need to free the corresponding watchpoint object.

Implement watchpoint

You need to implement the watchpoint-related functionality described above, and once you have implemented expression evaluation, the focus of the watchpoint implementation is on linked-list operations.

Since watchpoints need to be checked in every loop of cpu_exec(), this can be a significant performance overhead for the NEMU. We can put the watchpoint checking in trace_and_difftest() and wrap the watchpoint checking code in a new macro CONFIG_WATCHPOINT; then we can add a switch to watchpoints in nemu/Kconfig, and then turn on the switch via menuconfig to activate the watchpoints. When you don't need to use the watchpoint, you can turn off the switch in menuconfig to improve the performance of NEMU.

It is also possible to trigger more than two watchpoints at the same time, you are free to decide how to handle these special cases, we don't have a hard rule about this.

Debugging Tools and Principles

In the process of implementing watchpoints, you will most likely encounter segmentation errors. If you feel helpless, you should read this chapter carefully.

Let's take a quick look at why segmentation errors occur. First, the machine is always right. If something goes wrong in your program, first suspect a bug in your code. For example, if you inadvertently write something like if (p = NULL), but when you execute that line of code, all that happens is that p is assigned the value NULL, and the program goes on. However, when you dereference p in the future, it triggers an error and the program crashes.

We can abstract some software engineering related concepts from this example above:

Fault: Code that is implemented incorrectly, e.g. if (p = NULL).
Error: A state of the program execution that is not as expected, e.g., p is incorrectly assigned to NULL.
Failure: A directly observable error, such as a program triggering a segment error.

Debugging is actually a process of backtracking from the observed failure to find the fault, and after finding the fault, we quickly know how to fix the wrong code. But as you can see from the above example, debugging is not easy precisely because the following:

fault does not necessarily trigger an error right away
an error does not necessarily turn into an observable failure immediately after it is triggered
error will snowball, and by the time we see a failure, it's actually far from a fault.

Once we understand these reasons, we can formulate a strategy to:

turn as many faults as possible into errors. That's what tests do, so we've included an expression generator in the previous section to help you do that, and the labs that follow will provide a rich set of test cases. However, it's not always possible to turn every fault into an error, because that depends on the coverage of the tests. Designing a set of full-coverage tests is not a simple task, and the more complex the system, the more difficult it is to design full-coverage tests. However, the question of how to improve test coverage has long been a topic of academic interest.

How would you test your Watchpoint implementation?

We don't provide tests for watchpoints, so think about it, how would you test it?

Of course, for labs, testing as you go is a reasonable approach, depending on your confidence in your code.

Recognize error as early as possible. The moment you see an error is a direct determinant of how hard it is to debug: if you wait until a failure is triggered, it's harder to debug; but if you see an error just before it's triggered, it's much less difficult to debug. In fact, you've already seen some useful tools:
- -Wall, -Werror: turn potential faults into failures at compile time. These tools are limited in their usefulness, and can only look for faults that look suspicious even at compile time, such as if (p = NULL). However, as the compiler version is enhanced, the compiler can also find some undefined behavioropen in new window in the code. It's a free lunch, so it's a waste if you don't take it.
- assert(): turn an error into a failure at runtime. assert() is a simple but very powerful tool, as long as you define the characteristics that your program should satisfy, you will be able to intercept any error that doesn't satisfy those characteristics at runtime. For example, in the case of a linked list implementation, all we need to do is insert some simple assert() into the code (e.g., pointer dereference is not null), and we can pretty much say goodbye to segment errors. However, writing these assert()s requires some knowledge of the program's behavior, and assert()s have limited usefulness when the program's features are not easily expressed.
- printf(): Observe potential errors in the output. This is the most common tool for backtracking through a fault, to see if a variable in the program has entered an incorrect state. In NEMU we provide the macro Log() for outputting more debugging information, which actually wraps the functionality of printf(). However, since printf() requires a manual judgment of whether the output is correct or not, it is less convenient than the automatic judgment of assert().
- GDB: Observe any state of the program, anytime, anywhere. Debuggers are the most powerful tools, but they are also the most expensive to use because you need to watch for suspicious state in a sea of program states.

Powerful GDB

If you've encountered a segmentation fault, you've probably wondered which line of code triggered it. Try writing a program that triggers a segmentation fault, and then running it in GDB. Have you found any useful information that GDB can provide you with?

sanitizer - a low level assert

Segmentation fault are usually caused by illegal accesses, and a simple idea is that if we could check for out-of-bounds addresses with assert() before each access, we could catch segment errors before they occur!

Although we only need to focus on pointer and array accesses, there's a lot of code in the project like this, and it would be a pain in the ass to manually add assert() before these accesses. In fact, the compiler is in the best position to do this, since it knows where all the pointer and array accesses are. The compiler is made to support this by a tool called Address Sanitizer, which automatically inserts code to check for out-of-bounds before pointers and arrays are accessed. GCC provides a -fsanitize=address compilation option to enable this. Menuconfig has the option ready for you, you just need to turn it on:

Build Options
  [*] Enable address sanitizer

Then make clean and recompile.

You can try to trigger a segmentation fault on purpose, and then read the error message from Address Sanitizer. You may find that your program's performance is degraded because of the additional performance overhead of checking each access. But as a tool to help you diagnose bugs, it's worth the price, and you can still turn it off when you don't need to debug.

In fact, in addition to address out-of-bounds errors, Address Sanitizer also checks for use-after-free errors (i.e., "continue to use space after freeing it from the heap" errors), and do you know how it does this?

More sanitizers

In fact, GCC supports many more sanitizers that can check for different kinds of errors, you can check the -fsanitize option in man gcc. If your program works correctly with the various sanitizers on, it is a good sign that your program quality is still there.

Based on the above analysis, we can summarize some debugging suggestions:

Always use -Wall and -Werror.
Insert assert() into your code as often as possible.
Enable sanitizer as first step in debugging
When assert() fails to catch an error, output the suspicious variable via printf() in the hope that the error will be observed.
When printf() doesn't easily detect an error, use GDB to understand the exact behavior of the program.

If you've heard any of these suggestions in your programming classes, you'll have few runtime errors.

Breakpoint

The function of a breakpoint is to pause the program so that you can see the state of the program at any given moment. In fact, we can easily simulate breakpoints with watchpoints.

w $pc == ADDR

Where ADDR is the address where the breakpoint is set. This way the program will pause when it reaches ADDR.

How to improve the efficiency of breakpoints (recommended to think about in the second cycle)

If you use breakpoints when running larger programs (such as microbench), you may find that setting breakpoints significantly reduces the efficiency of NEMU's program execution. Think about why this is the case. Is there any way to solve this problem?

The way the debugger works with breakpoints is very different from the above method of simulating breakpoints through watchpoints. In fact, the way breakpoints work, is the 36 Stratagems of Steal the Dragon and Replace with the Phoenix! If you want to unravel this mystery, you can read this articleopen in new window. Once you understand how breakpoints work, try to think about the following two questions.

Can't be any longer?

The x86 int3 instruction does not have any operands, the opcode is 1 byte, so the length of the instruction is 1 byte. Is this necessary? Suppose there is a variant of the x86 architecture, my-x86, which is the same as x86 except that the length of the int3 instruction becomes 2 bytes. In my-x86, would the breakpoint mechanism in the above article still work? Why?

Freeform Breakpoints

What happens if you set a breakpoint at a non-first byte (middle or end) of an instruction? You can try this in GDB, and then think about it and explain why.

The Past and Present of NEMU

You already know how NEMU works. In fact, before NEMU was born, NEMU wasn't called NEMU for a while, it was called NDB (NJU Debugger), and then it was renamed to NEMU for some reason. If you want to know this prehistoric secret, the first thing you need to know is: what is the difference between an Emulator and a Debugger? More specifically, how does GDB debug a program compared to NEMU?

# Watch Point

# Extending the functionality of expression evaluation

Extending the functionality of expression evaluation

Expression evaluation in riscv64

Limitation of testing

# implement watchpoints

Implement watchpoint pool management logic

Recall the past to understand the future

Implement watchpoint

# Debugging Tools and Principles

How would you test your Watchpoint implementation?

Powerful GDB

sanitizer - a low level assert

More sanitizers

# Breakpoint

How to improve the efficiency of breakpoints (recommended to think about in the second cycle)

Can't be any longer?

Freeform Breakpoints

The Past and Present of NEMU

Watch Point

Extending the functionality of expression evaluation

implement watchpoints

Debugging Tools and Principles

Breakpoint