A linked list is a data structure that consists of a sequence of data records, and each record includes a field that contains a reference (link) to the next record in the sequence. The principal benefit of using a linked list over an array is that the order of the linked items can differ from the order in which the data items are stored in memory or on disk. Therefore, linked lists allow the insertion and removal of nodes at any point in the list.
Example 6-29 shows a C code example of a linked list
and its traversal. This linked list consists of a series of node structures named pnode
, and it is manipulated with two loops. The first loop at ❶ creates 10 nodes and fills them with data. The second loop at
❷ iterates over all the records and prints their
contents.
Example 6-29. C code for a linked list traversal
struct node { int x; struct node * next; }; typedef struct node pnode; void main() { pnode * curr, * head; int i; head = NULL; for(i=1;i<=10;i++) ❶ { curr = (pnode *)malloc(sizeof(pnode)); curr->x = i; curr->next = head; head = curr; } curr = head; while(curr) ❷ { printf("%d ", curr->x); curr = curr->next ; } }
The best way to understand the disassembly is to identify the two code constructs within
the main
method. And that is, of course, the crux of this
chapter: Your ability to recognize these constructs makes the analysis easier.
In Example 6-30, we identify the for
loop first. var_C
corresponds to
i
, which is the counter for the loop. var_8
corresponds to the head
variable, and var_4
is the curr
variable. var_4
is a pointer to a struct with two variables that are assigned values
(shown at ❶ and ❷).
The while
loop (❸ through ❺) executes the iteration through
the linked list. Within the loop, var_4
is set to the next record
in the list at ❹.
Example 6-30. Assembly code for the linked list traversal example in Example 6-29
0040106A mov [ebp+var_8], 0 00401071 mov [ebp+var_C], 1 00401078 00401078 loc_401078: 00401078 cmp [ebp+var_C], 0Ah 0040107C jg short loc_4010AB 0040107E mov [esp+18h+var_18], 8 00401085 call malloc 0040108A mov [ebp+var_4], eax 0040108D mov edx, [ebp+var_4] 00401090 mov eax, [ebp+var_C] 00401093 mov [edx], eax ❶ 00401095 mov edx, [ebp+var_4] 00401098 mov eax, [ebp+var_8] 0040109B mov [edx+4], eax ❷ 0040109E mov eax, [ebp+var_4] 004010A1 mov [ebp+var_8], eax 004010A4 lea eax, [ebp+var_C] 004010A7 inc dword ptr [eax] 004010A9 jmp short loc_401078 004010AB loc_4010AB: 004010AB mov eax, [ebp+var_8] 004010AE mov [ebp+var_4], eax 004010B1 004010B1 loc_4010B1: 004010B1 cmp [ebp+var_4], 0 ❸ 004010B5 jz short locret_4010D7 004010B7 mov eax, [ebp+var_4] 004010BA mov eax, [eax] 004010BC mov [esp+18h+var_14], eax 004010C0 mov [esp+18h+var_18], offset aD ; "%d " 004010C7 call printf 004010CC mov eax, [ebp+var_4] 004010CF mov eax, [eax+4] 004010D2 mov [ebp+var_4], eax ❹ 004010D5 jmp short loc_4010B1 ❺
To recognize a linked list, you must first recognize that some object contains a pointer that points to another object of the same type. The recursive nature of the objects is what makes it linked, and this is what you need to recognize from the disassembly.
In this example, realize that at ❹, var_4
is assigned eax
, which comes from
[eax+4]
, which itself came from a previous assignment of var_4
. This means that whatever struct var_4
is must contain a pointer 4 bytes into it. This points to another struct that must
also contain a pointer 4 bytes into another struct, and so on.
3.143.237.136