Saltar a contenido

Proyecto 1: C y RISC-V

Objetivos

  • Mejorar sus habilidades de programación en C.
  • Conocer algunos de los detalles de RISC-V.
  • Prepararse para lo que viene más adelante en el curso.

Conocimientos previos

Para realizar este proyecto ustedes tienen que tener claros algunos conceptos, de lo contrario será bastante difícil e incómodo empezar a trabajar. Les recomendamos que antes de empezar estén totalmente seguros que dominan al 100% los siguientes puntos:

  • Operaciones binarias en C (xor, or, and, etc).
  • Operaciones aritméticas con signo y sin signo en C.
  • Type casting en C.
  • Control de flujo en C (switch, if, etc).
  • Funciones en C.
  • Entender qué son las estructuras (struct) en C.
  • Entender cómo funcionan las uniones (union) en C.
  • Uso correcto de printf.
  • Entender la estructura del set de instrucciones de RISC-V.
  • Programar en lenguaje ensamblador RISC-V.

Si creen que no tienen claro alguno de estos temas al 100%, por favor no duden en ir a consultar los libros y material correspondiente del curso, por ejemplo K&R, es indispensable. En Lecturas Recomendadas pueden encontrar algunas lecturas que tocan los puntos antes mencionados y otras cosas que también les pueden servir, nunca está demás tener un poco más de información.

Lecturas Recomendadas

RISCV Book KR PH

  • Guía Práctica de RISC-V: 2
  • K&R: 6
  • P&H: B-43

Introducción

En este proyecto ustedes deben de crear un emulador que pueda ejecutar un subconjunto de instrucciones de RISC-V. Ustedes se van a encargar de hacer un programa que decodifique y ejecute varias instrucciones de RISC-V. Considérenlo como una versión miniatura de Jupiter.

RISC-V Green Card

Se recomienda que tenga impresa su Green Card para consultar fácilmente los opcode, func3, func7, etc.

Berkeley Green Card

Preparación

Antes de comenzar asegúrense de que hayan leído y comprendido todas las instrucciones del proyecto de principio a fin. Si tienen alguna pregunta pueden consultar la sección de preguntas frecuentes para ver si ya ha sido resuelta, de lo contrario por favor diríjanse a Slack y pregunten en los canales correspondientes.

Para comenzar con el proyecto, primero tienen que tener todos los archivos base, estos se encuentran aquí. Pueden trabajar en parejas o de forma individual, por lo que al aceptar la asignación les preguntará si desean crear un grupo nuevo o unirse a uno ya existente. Si crean un grupo nuevo, ingresen un nombre que represente al grupo y que no esté ya en los grupos existentes. Use un nombre bonito y creativo! (Alguna referencia a su equipo deportivo favorito, alguna canción que les guste, su carta favorita de Magic, algún anime, lo que quiera siempre y cuando no sea ofensivo) No use nombres aburridos como "Proyecto 1", "CC3 - Seccion X", etc. POR FAVOR.

Create group

Si desean unirse a un grupo ya creado, tienen que buscar el nombre del grupo y pulsar el botón que dice join

Join group

Tienen que tener mucho cuidado al unirse a un grupo ya existente, pues al unirse tendrá acceso inmediato al código que ya esté subido por parte del otro grupo. Si se une a un grupo incorrecto lo consideraremos como PLAGIO pues podrían pasar robando código de esta manera.

Ya sea que se unan o creen un nuevo grupo, al finalizar el proceso les creará automáticamente un repositorio con una extensión que termina con su nombre de grupo. Ya habiendo hecho todo eso, pueden ejecutar los siguientes comandos abriendo una terminal (CTRL + T):

git clone <link del repositorio>

NOTA: Tienen que reemplazar <link del repositorio> con el link del repositorio que se creó.

Estructura del proyecto

Cuando hayan clonado el repositorio, van a encontrar los siguientes archivos:

Makefile
part1.c  
part2.c  
README.md  
riscv.c  
riscvcode/
riscv.h  
submit  
types.h  
utils.c  
utils.h

Los únicos archivos que pueden modificar son:

  • utils.c: Archivo auxiliar que contendrá varias funciones de ayuda para la parte 1 y 2 del proyecto.
  • part1.c: Este es el archivo que van a modificar en la parte 1 del proyecto.
  • part2.c: Este es el archivo que van a modificar en la parte 2 del proyecto.

Ustedes NO pueden crear otros archivos ni crear archivos de cabecera .h. Si necesitan agregar funciones de ayuda, por favor colóquenlas en los archivos C correspondientes (utils.c, part1.c, part2.c). Si ustedes no siguen estas recomendaciones, su código fallará en el autograder y obtendrán 0 como nota.

Otros archivos que necesitan consultar detenidamente para entender el proyecto:

  • type.h: Archivo de cabecera que tiene los tipos de datos que ustedes van a utilizar.
  • Makefile: Para compilar y probar su código.
  • riscvcode/*: Archivos para hacer algunas pruebas.
  • utils.h: Archivo que contiene el formato de las instrucciones a ser utilizadas en la parte 1 del proyecto.

Archivos que no es necesario que los revisen, pero si son curiosos:

  • riscv.h: tiene declaraciones de funciones que se utilizan en la parte 1 y 2 del proyecto.
  • riscv.c: programa encargado de probar la parte 1 y 2 del proyecto, el simulador como tal.

El emulador de RISC-V

Los archivos proporcionados en el repositorio que crearon con GitHub Classroom son la base para un emulador de RISC-V. Primero, ustedes deberán agregar código en part1.c y utils.c para imprimir las instrucciones en ensamblador correspondientes al código de máquina (binario). Una vez realizaron esto, ustedes completarán el programa agregando código en el archivo parte2.c para ejecutar cada instrucción (incluyendo los accesos a memoria). Su simulador debe de ser capaz de entender cada una de las instrucciones siguientes ya codificadas en código de máquina (binario), nosotros ya les damos una tabla de los tipos de instrucciones que debe de ser capaz de manejar su emulador.

Es muy importante que ustedes lean y entiendan las definiciones encontradas en types.h antes de empezar su proyecto. Si tiene alguna duda, o encuentran algo que no entiendan respecto a las mismas consulten el capítulo 6 de K&R, que habla sobre estructuras, bitfields y uniones.

Set de Instrucciones

El set de instrucciones que su emulador debe soportar esta listado a continuación. Toda la información acá es copiada desde RISC-V green card, como ayuda adicional pueden utilizar la hoja proporcionada anteriormente.

Tipo R

FORMATO DE UNA INSTRUCCIÓN DE TIPO R
R-TYPE funct7 rs2 rs1 funct3 rd opcode
Bits 7 5 5 3 5 7
INTRUCCIONES TIPO R (OPCODE 0x33)
INSTRUCCIÓN FUNCT3 FUNCT7/IMM OPERACIÓN
add rd, rs1, rs2 0x0 0x00 R[rd]<-R[rs1] + R[rs2]
mul rd, rs1, rs2 0x0 0x01 R[rd]<-(R[rs1] * R[rs2]) [31:0]
sub rd, rs1, rs2 0x0 0x20 R[rd]<-R[rs1] - R[rs2]
sll rd, rs1, rs2 0x1 0x00 R[rd]<-R[rs1] << R[rs2]
mulh rd, rs1, rs2 0x1 0x01 R[rd]<-(R[rs1] * R[rs2]) [63:32]
slt rd, rs1, rs2 0x2 0x00 R[rd]<-(R[rs1] < R[rs2]) ? 1 : 0
xor rd, rs1, rs2 0x4 0x00 R[rd]<-R[rs1] ^ R[rs2]
div rd, rs1, rs2 0x4 0x01 R[rd]<-R[rs1] / R[rs2]
srl rd, rs1, rs2 0x5 0x00 R[rd]<-R[rs1] >> R[rs2]
sra rd, rs1, rs2 0x5 0x20 R[rd]<-R[rs1] >> R[rs2]
or rd, rs1, rs2 0x6 0x00 R[rd]<-R[rs1] | R[rs2]
rem rd, rs1, rs2 0x6 0x01 R[rd]<-R[rs1] % R[rs2]
and rd, rs1, rs2 0x7 0x00 R[rd]<-R[rs1] & R[rs2]

Tipo I

FORMATO DE UNA INSTRUCCIÓN DE TIPO I
I-TYPE imm[11:0] rs1 funct3 rd opcode
Bits 12 5 3 5 7
INTRUCCIONES TIPO I (OPCODE 0x03)
INSTRUCCIÓN FUNCT3 FUNCT7/IMM OPERACIÓN
lb rd, offset(rs1) 0x0 R[rd]<- SignExt(Mem(R[rs1] + offset, byte))
lh rd, offset(rs1) 0x1 R[rd]<- SignExt(Mem(R[rs1] + offset, half))
lw rd, offset(rs1) 0x2 R[rd]<- Mem(R[rs1] + offset, word)
INTRUCCIONES TIPO I (OPCODE 0x13)
INSTRUCCIÓN FUNCT3 FUNCT7/IMM OPERACIÓN
addi rd, rs1, imm 0x0 R[rd]<- R[rs1] + imm
slli rd, rs1, imm 0x1 0x00 R[rd]<- R[rs1] << imm
slti rd, rs1, imm 0x2 R[rd]<- (R[rs1] < imm) ? 1 : 0
xori rd, rs1, imm 0x4 R[rd]<- R[rs1] ^ imm
srli rd, rs1, imm 0x5 0x00 R[rd]<- R[rs1] >> imm
srai rd, rs1, imm 0x5 0x20 R[rd]<- R[rs1] >> imm
ori rd, rs1, imm 0x6 R[rd]<- R[rs1] | imm
andi rd, rs1, imm 0x7 R[rd]<- R[rs1] & imm
INTRUCCIONES TIPO I (OPCODE 0x67)
INSTRUCCIÓN FUNCT3 FUNCT7/IMM OPERACIÓN
jalr 0x0 R[rd]<- PC + 4
PC<- R[rs1] + imm
INTRUCCIONES TIPO I (OPCODE 0x73)
INSTRUCCIÓN FUNCT3 FUNCT7/IMM OPERACIÓN
ecall 0x0 0x000 (Transfiere el control al Sistema Operativo)
a0 = 1 imprime el valor contenido en a1 como entero.
a0 = 10 es exit o un indicador de final de código.

Tipo S

FORMATO DE UNA INSTRUCCIÓN DE TIPO S
S-TYPE imm[11:5] rs2 rs1 funct3 imm[4:0] opcode
Bits 7 5 5 3 5 7
INTRUCCIONES TIPO S (OPCODE 0x23)
INSTRUCCIÓN FUNCT3 FUNCT7/IMM OPERACIÓN
sb rs2, offset(rs1) 0x0 Mem(R[rs1] + offset)<- R[rs2][7:0]
sh rs2, offset(rs1) 0x1 Mem(R[rs1] + offset)<- R[rs2][15:0]
sw rs2, offset(rs1) 0x2 Mem(R[rs1] + offset)<- R[rs2]

Tipo SB

FORMATO DE UNA INSTRUCCIÓN DE TIPO SB
SB-TYPE imm[12] imm[10:5] rs2 rs1 funct3 imm[4:1] imm[11] opcode
Bits 1 6 5 5 3 4 1 7
INTRUCCIONES TIPO SB (OPCODE 0x63)
INSTRUCCIÓN FUNCT3 FUNCT7/IMM OPERACIÓN
beq rs1, rs2, offset 0x0 if(R[rs1] == R[rs2])
PC<- PC + {offset, 1b'0}
bne rs1, rs2, offset 0x1 if(R[rs1] != R[rs2])
PC<- PC + {offset, 1b'0}

Tipo U

FORMATO DE UNA INSTRUCCIÓN DE TIPO U
U-TYPE imm[31:12] rd opcode
Bits 20 5 7
INTRUCCIONES TIPO U (OPCODE 0x17)
INSTRUCCIÓN FUNCT3 FUNCT7/IMM OPERACIÓN
auipc rd, offset R[rd]<- PC + {offset, 12b'0}
INTRUCCIONES TIPO U (OPCODE 0x37)
INSTRUCCIÓN FUNCT3 FUNCT7/IMM OPERACIÓN
lui rd, offset R[rd]<- {offset, 12b'0}

Tipo UJ

FORMATO DE UNA INSTRUCCIÓN DE TIPO UJ
UJ-TYPE imm[20] imm[10:1] imm[11] imm[19:12] rd opcode
Bits 1 10 1 8 5 7
INTRUCCIONES TIPO UJ (OPCODE 0x6F)
INSTRUCCIÓN FUNCT3 FUNCT7/IMM OPERACIÓN
jal rd, imm R[rd]<- PC + 4
PC<- PC + {imm, 1b'0}

Al igual que la arquitectura RISC-V normal, el sistema RISC-V que están implementando es little-endian. Esto significa que cuando se le da un valor compuesto de múltiples bytes, el byte menos significativo se almacena en la dirección más baja.

Estructura del código

El código base que les fue proporcionado funciona de la siguiente manera:

  1. Lee los programas en código de máquina que se encuentran en la memoria (Empezando en la dirección 0x01000). Para "ejecutar" el programa este es pasado como un parámetro en la línea de comandos. Cada programa tiene 1 MiB de memoria y la unidad mínima de direccionamiento son los bytes.
  2. Todos los registros de RISC-V son inicializados en 0 y el program counter (PC) hacia la dirección 0x01000. Las únicas excepciones a las inicializaciones antes mencionadas son el stack pointer (sp) que tiene un valor inicial de 0xEFFFF y el global pointer (gp) que tiene un valor inicial de 0x03000. En el contexto de su emulador, el global pointer hace referencia a la sección estática de su memoria. Los registros y el program counter están definidos en el Processor struct definido en types.h.
  3. Se definieron banderas con las cuales puede manejar la interacción con el usuario. Dependiendo de la opción especificada en la línea de comandos, el simulador mostrará un dissassembly dump (-d) o se ejecutará el programa. Habrá más información sobre las opciones de línea de comandos más adelante.

Luego se entra al flujo de simulación principal, el cual ejecuta una instrucción tras otra hasta que la simulación se completa. La ejecución de una instrucción realiza las siguientes tareas:

  1. Trae una instrucción desde la memoria, usando el pc como dirección (fetch).
  2. Examina el opcode/funct3 para determinar que instrucción es (decode).
  3. Ejecuta la instrucción y actualiza el pc (execute).

Opciones en la línea de comandos

  • -d: Indica al simulador que desensamble el programa completo y que termine sin ejecutarlo.
  • -i: Corre el simulador en modo interactivo (interactive), es decir que se ejecutará una instrucción a la vez al presionar enter. Cada instrucción es mostrada en su forma desensamblada.
  • -t: Corre el simulador en modo rastreo (trace), en donde cada instrucción es ejecutada y es mostrada al usuario.
  • -r: Indica al simulador que imprima el contenido de los 32 registros después de que es ejecutada cada instrucción. Esta opción es más útil cuando se combina con la opción -i.

En la parte 2, ustedes deberán implementar los siguientes métodos:

  • El execute_instruction().
  • Los diferentes executes.
  • El store().
  • El load().

Para cuando ustedes hayan terminado la implementación de todos los métodos, el simulador será capaz de manejar todas las instrucciones de la tabla anterior.

Parte 1

Su primera tarea es implementar un desensamblador al completar el método decode_instruction() en el archivo part1.c junto a otras funciones.

El objetivo de esta parte, es que, dada una instrucción en código de máquina, ustedes deberán traducirla a su instrucción en lenguaje ensamblador RISC-V (e.g. add x1, x2, x3 ). Para esta parte, ustedes no harán referencia a los registros por nombre propio sino por su nombre genérico (es decir, x0, x1, ..., x31). Cuando impriman las instrucciones revisen las constantes definidas en utils.h, ya que estas le pueden ser de ayuda. Más detalles sobre los requisitos a continuación.

Requisitos parte 1

  1. Imprimir el nombre de la instrucción. Si la instrucción tiene argumentos, impriman un tab (\t). HINT: este tab ya viene incluído en los FORMAT que encuentra en utils.
  2. Imprimir todos los argumentos, siguiendo el orden y formato dado en la columna de INSTRUCCIÓN de las tablas mostradas anteriormente.
    • Los argumentos son generalmente separados por coma (lw/sw, usan también paréntesis), pero no están separados por espacios.
    • Ustedes encontrarán de ayuda revisar el archivo utils.h.
    • Los registros que son argumentos de la instrucción son impresos con una x seguido del número de registro, en decimal. (e.g. x0 o x31)
    • Todos los inmediatos deben mostrarse como un número decimal con signo.
    • Los corrimientos (e.g. para slli) se imprimen como números decimales sin signo (e.g. 0 a 31).
  3. Imprimir un salto de línea (\n) al final de cada instrucción.
  4. Se estará utilizando un autograder para calificar esta tarea. Si su output difiere del nuestro debido a errores de formato, no obtendrán nota.
  5. Nosotros les proveemos ciertas pruebas. Sin embargo, dado que estas pruebas sólo cubren un subconjunto de todos los escenarios posibles, pasar estas pruebas no significa que su código esté libre de errores. Ustedes deberán identificar todos los casos y probarlos.

Para completar la funcionalidad de la parte 1, deben de completar lo siguiente:

  • La función decode_instrucction() en part1.c.
  • Los diferentes writes en part1.c.
  • Los diferentes prints en part1.c.
  • Los diferentes gets en utils.c.
  • La función bitExtender, get_x_distance y get_memory_offset en utils.c.

Ustedes deben de correr el test brindado para su proyecto escribiendo el siguiente comando. Si ustedes pasan el test, verán en su consola el siguiente output.

make part1
gcc -g -Wall -Werror -Wfatal-errors -O2 -o riscv utils.c part1.c part2.c riscv.c
simple_disasm TEST PASSED!
multiply_disasm TEST PASSED!
random_disasm TEST PASSED!
---------Disassembly Tests Complete---------

Probando la parte 1

El make part1 prueba su proyecto solo con algunos archivos sencillos. Puede consultar la carpeta riscvcode para ver que otros testcases hay, si quiere probar alguno específico use el comando:

make [test_name]_disasm

Si quiere que estos testcases adicionales se prueben cada vez que ejecute make part1, vaya al Makefile y agreguelos en la línea que dice ASM_TEST.

SOURCES := utils.c part1.c part2.c riscv.c
HEADERS := types.h utils.h riscv.h

ASM_TESTS := simple multiply random test_name

Si su instrucción desensamblada no es igual a la esperada, ustedes obtendrán la diferencia entre el output esperado y el output que devolvieron.

# Output esperado
< 00001014: lui x8, 1048575
---
# Output devuelto
> 00001014: Invalid Instruction: 0xfffff437

Parte 2

Su segunda tarea es completar el emulador implementando los métodos execute_instruction(). execute()'s, store() y load() del archivo part2.c.

Requisitos

Esta parte consistirá en implementar la funcionalidad de cada instrucción. Por favor implementen las funciones descritas a continuación (todas en part2.c):

  • execute_instruction(): Ejecuta la instrucción proporcionada como parámetro. Esta debería modificar los registros apropiados, realizar las llamadas a memoria necesarias y actualizar el program counter para apuntar a la siguiente instrucción a ejecutar.

  • execute()'s: Varias funciones de ayuda para ser llamadas en ciertas condiciones para ciertas instrucciones. Es su decisión usar estas funciones, pero estas les ayudarán de gran manera a organizar el código.

  • store(): Toma una dirección, un tamaño, un valor y almacena los primeros (tamaño) bytes del valor dado en la dirección dada. Cuando el parámetro check_align sea 1 se validarán las restricciones de alineación. Se incluyó este parámetro para obligar a las instrucciones a estar alineadas por palabras de memoria (word-aligned). Cuando implementen el store y load, este parámetro debe ser 0 dado que RISC-V no hace cumplir las restricciones de alineación.

  • load(): Toma una dirección y un tamaño, y retorna los siguientes (tamaño) bytes empezando en la dirección dada. El check_align funciona de la misma forma que en store().

Probando la Parte 2

Les hemos adjuntado un self-checking assembly test que prueba varias de las instruciones, sin embargo este test no es exhaustivo y no prueba todas las instrucciones. A continuación, se ejemplifica cómo ejecutar los test (el output es de una solución correcta).

make part2
gcc -Wall -Werror -Wfatal-errors -O2 -o riscv utils.c part1.c part2.c riscv.c
simple_execute TEST PASSED!
multiply_execute TEST PASSED!
random_execute TEST PASSED!
-----------Execute Tests Complete-----------

Lo más probable es que ustedes tenga errores al empezar a realizar la parte 2, entonces prueben el modo de rastreo (trace) descrito en Opciones en la línea de Comandos.

Al igual que en la parte 1, el comando make part2 hace solo algunas pruebas sencillas. Para usar los demás testcases que encontró en la carpeta riscvcode use el siguiente comando.

make [test_name]_execute

Preguntas Frecuentes

1. ¿Cómo puedo empezar?

Lo mejor es revisar types.h y analizar la estructura Instruction para empezar a trabajar en la parte1.c, por ejemplo como acceder a cada campo de cada diferente tipo de instrucción y al opcode también. Por ejemplo, para acceder al opcode pueden utilizar:

instruction.opcode

siendo instruction una variable que representa una "instancia" de la estructura Instruction. Luego de esto, pueden ver cómo accediendo a estos campos pueden decodificar la instrucción y así lograr imprimirla.

2. Me da Floating-point Exception (core dumped) al hacer algunas operaciones aritméticas, ¿por qué?

Generalmente esto se da porque se divide por 0 o hay overflow utilizando variables enteras con signo. Por ejemplo:

int x = 10;
int y = 0;
int z = x / y;
int32_t x = 0x80000000;
int32_t y = 0xffffffff;
int32_t z = x / y;

La solución para la división por 0 es simplemente tienen que devolver -1 como dice la especificación de RISC-V y para el residuo devolver el primer argumento de la operación. En el caso de overflow devolvemos rs1 para la division y 0 para el residuo.

// division
if (rs2 == 0) {
    rd = -1;                // division entre cero
} else if (rs1 == 0x80000000 && rs2 == 0xffffffff) {
    rd = rs1;               // overflow
} else {
    rd = rs1 / rs2;
}
// residuo
if (rs2 == 0) {
    rd = rs1;               // residuo entre cero
} else if (rs1 == 0x80000000 && rs2 == 0xffffffff) {
    rd = 0;                 // overflow
} else {
    rd = rs1 % rs2;
}

3. En la parte 1 el formato nunca es el esperado por las pruebas, ¿por qué?

Seguramente no están utilizando el formato correcto, les recomendamos que utilicen las siguientes macros para imprimir las instrucciones que se encuentran en el archivo utils.h:

#define RTYPE_FORMAT "%s\tx%d, x%d, x%d\n"
#define ITYPE_FORMAT "%s\tx%d, x%d, %d\n"
#define JALR_FORMAT "jalr\tx%d, x%d, %d\n"
#define MEM_FORMAT "%s\tx%d, %d(x%d)\n"
#define AUIPC_FORMAT "auipc\tx%d, %d\n"
#define LUI_FORMAT "lui\tx%d, %d\n"
#define JAL_FORMAT "jal\tx%d, %d\n"
#define BRANCH_FORMAT "%s\tx%d, x%d, %d\n"
#define ECALL_FORMAT "ecall\n"

4. ¿Puedo crear mis propias funciones?

Sí, siempre y cuando estas estén declaradas, ya sea en part1.c, part2.c o utils.c, ya que son los únicos archivos que se envían al autograder. Sin embargo, NO está permitido renombrar o eliminar las siguientes funciones:

/* archivo part1.c */
void decode_instruction(Instruction i);

/* archivo part2.c */
void execute_instruction(Instruction instruction, Processor* processor, Byte *memory);
void store(Byte *memory, Address address, Alignment alignment, Word value, int);
Word load(Byte *memory, Address address, Alignment alignment, int);

Ya que el simulador riscv.c espera que estas estén definidas.

Revisando su nota

Haga pruebas sencillas antes de usar el autograder, ya que este prueba de una vez todos los casos posibles. Para utilizarlo, use el comando que ya conoce.

./check

Recuerde hacer add + commit + push frecuentemente. Si algo le pasa a su máquina virtual, puede ir a Github a recuperar lo que ya haya subido.

Al terminar AMBOS INTEGRANTES DEL GRUPO deben subir el link del repositorio al GES.