Sistemski softver/Jun 2022

Ispit u junskom ispitnom roku 2022. godine održan je 16. juna. Trajao je 2 sata i radio se u vežbankama.

1. zadatak

Postavka

Posmatra se proces asembliranja datog ivzornog asemblerskog koda za amd64 arhitekturu. Rezultat asembliranja je predmetni program po ELF formatu. Prikazati sadržaj (1) tabele simbola i (2) relokacionih zapisa strogo poštujući školski format i obavezno u skladu sa zadatom numeracijom simbola.

.intel_syntax noprefix
.section .text
.global min, la1
min: enter 0, 0          # 0x00
     mov rbx, la1        # 0x04
     cmp rbx, [rbp]+0x12 # 0x0c
     call var[rip]       # 0x10
     jle la1             # 0x16
     mov rax, [rbp]+0x12 # 0x18
     jmp la2             # 0x1c
la1: mov rax, rbx        # 0x1e
la2: leave               # 0x21
     ret                 # 0x22

.data
.global var
.type var, @object
var:
.quad la1, la2-4
.end

Napomena: heksadecimalni brojevi navedeni u komentaru izvornog asemblerskog koda predstavljaju pomeraj do početka instrukcije u tom redu gledano od početka sekcije kojoj instrukcija pripada. Takođe, usvojiti pretpostavku da je veličina operacionog koda:

• 2B za instrukciju call za PC relativno adresiranje,
• 4B za instrukciju mov za apsolutno adresiranje i
• 1B za instrukcije jle i jmp za PC relativno adresiranje.

Rešenje

.symtab

Num	Value	Size	Type	Bind	Ndx	Name
0:	0	0	NOTYP	LOC	UND
1:	0	0	SCTN	LOC	1	.text
2:	0	0	SCTN	LOC	2	.data
3:	0	0	SCTN	LOC	3	.bss
4:	21	0	NOTYP	LOC	1	la2
5:	0	0	NOTYP	GLOB	1	min
6:	1E	0	NOTYP	GLOB	1	la1
7:	0	0	OBJ	GLOB	2	var

Iako nije prikazano u školskom formatu, simboli označeni preko .type simbol, @object imaju tip OBJECT u GNU asembleru.

.rela.text

Offset	Type	Symbol	Addend
8	R_X86_64_32	6 (la1)	0
12	R_X86_64_PC32	7 (var)	-4
17	R_X86_64_PC8	6 (la1)	-1
1D	R_X86_64_PC8	1 (.text)	20

Relokacioni zapisi na 17 i 1D ne moraju da postoje, pošto se pomeraj može ugraditi i tokom asembliranja.

.rela.data

Offset	Type	Symbol	Addend
0	R_X86_64_64	6 (la1)	0
8	R_X86_64_64	1 (.text)	1D

2. zadatak

Postavka

U C pretprocesoru treba napisati makri definiciju REPEAT(str, n) koja kao svoj rezultat daje string str nadovezan n puta na samog sebe za vrednosti parametra n između 0 i 5. Na primer, makro poziv REPEAT("ha ", 3) rezultuje stringom "ha ha ha ". Treba imati na umu da C pretprocesor ne dozvoljava rekurziju (makro ne može rekurzivno pozvati samog sebe) niti dozvoljava korišćenje #if u telu makroa.

Rešenje

#define REP0(X)
#define REP1(X) X
#define REP2(X) REP1(X) X
#define REP3(X) REP2(X) X
#define REP4(X) REP3(X) X
#define REP5(X) REP4(X) X
#define REPEAT(str, n) REP##n(str)

Pri pozivu REPEAT("ha ", 3) makroprocesor će generisati "ha " "ha " "ha " što je ekvivalentno stringu "ha ha ha " (tako funkcioniše konkatenacija string literala u C). Ovo ponašanje je bilo napomenuto na ispitu.

3. zadatak

Postavka

Zadati moduli main.c i other.c odvojeno se prevode i potom statički povezuju u jedinstvenu izvršnu datoteku pomoću GNU lanca alata. Prilikom povezivanja ne koriste se drugi moduli niti biblioteke. Treba popuniti svaki od komentara /* ??? */ u datoteci other.c jednom od navedenih oznaka koje definišu kakav efekat izaziva deklaracija koja prethodi komentaru na datoj liniji:

• OK-GLB: ovo je ispravna deklaracija promenljive koja je globalna i za main.c i za other.c (globalna u smislu da će se promena koju napravi foo() funkcija korektno reflektovati i u main() funkciji kao i obrnuto),
• OK-LOC: ovo je ispravna deklaracija promenljive koja je lokalna samo za foo() (lokalna u smislu da se bilo koja promena koju napravi foo() funkcija neće reflektovati na main() funkciju),
• CMPL_E: ova deklaracija će izazvati prijavu greške od strane prevodioca (linker neće biti ni pokrenut),
• LINK_E: ova deklaracija će izazvati prijavu greške od strane linkera (obe datoteke biće prevedene bez greške, ali linker će prijaviti grešku prilikom povezivanja na simbolu na datoj liniji),
• SMNT_E: ova deklaracija neće izazvati prijavu nikakve greške (ni prevodioca niti linkera), ali će program imati semantičku grešku odnosno logičku neispravnost koja se može manifestovati tokom njegovog izvršavanja i
• OTHR_E: dešava se neka druga greška koja nije pokrivena prethodnim slučajevima.

// file main.c
extern int a;
static double b;
int help; int *c = &help;
struct
{
  double d;
} e;
int f = 0;
double g = 0.1;
#define h 99
int i;
unsigned j;

int main() {
  // ...
}

// file other.c
double a;       /* ??? */
double b;       /* ??? */
int *c;         /* ??? */


double d;       /* ??? */
int e = 0;      /* ??? */
int f;          /* ??? */
double g = 0.1; /* ??? */
int h = 99;     /* ??? */
unsigned *i;    /* ??? */
static int j;   /* ??? */

int foo() {
  // ...
}

Rešenje

main.c	other.c	Klasifikacija
extern int a;	double a;	SMNT_E
static double b;	double b;	OK-LOC
int help; int *c = &help;	int *c;	OK-GLB
struct { double d;	double d;	OK-LOC
} e;	int e = 0;	SMNT_E
int f = 0;	int f;	OK-GLB
double g = 0.1;	double g = 0.1;	LINK_E
#define h 99	int h = 99;	OK-LOC
int i;	unsigned *i;	SMNT_E
unsigned j;	static int j;	OK-LOC

4. zadatak

Postavka

Posmatra se JIT emulator i emuliranje sledećeg programa.

1. Označiti sve blokove koji će u toku rada emulatora biti prevedeni. Za svaki prevedeni blok navesti jedinstvenu identifikaciju u obliku B<n>(<x>-<y>) (<n> je redni broj bloka u pogledu trenutka njegovog prevođenja pri čemu numeracija počinje od broja jedan, <x> je redni broj prve a <y> redni broj poslednje linije izvornog koda bloka).
2. Navesti sekvencu izvršavanja. U sekvenci izvršavanja mogu se nađi samo GP (svaki put kada se emulator vrati u glavnu petlju), BH (svaki put kada se pozove funkcija koja pomaže u razrešavanju skokova) i B<n> (svaki put kada se izvrši dati blok u skladu sa oznakama iz prethodne tačke).

      BEG       ; line  1
      LDI 2     ; line  2   ( PZ) A <= <V>
  L1  SUB B     ; line  3   (CPZ) A <= A - mem[<V>]
  L2  ADD C     ; line  4   (CPZ) A <= A + mem[<V>]
      BNG L2    ; line  5         if (!flags[P]) PC <= <V>
      BZE L3    ; line  6         if ( flags[Z]) PC <= <V>
      SBI 2     ; line  7   (CPZ) A <= A - <V>
      BNZ L1    ; line  8         if (!flags[Z]) PC <= <V>
  L3  HLT       ; line  9         stop execution
  B   DC 9      ; line 10
  C   DC 2      ; line 11
      END       ; line 12

Rešenje

1. Blokovi po redosledu dodavanja u tabelu (B3 je dodat u tabelu dok još nije bio preveden):
   1. B0(1-5)
   2. B1(4-5)
   3. B2(6-6)
   4. B3(9-9)
   5. B4(7-8)
   6. B5(3-3)
2. Redosled izvršavanja:
   1. GP
   2. B0
   3. BH
   4. GP
   5. B1
   6. BH (ukoliko se prilikom prevođenja B1 nije izvršila optimizacija da se umesto branch helper ugradi skok na B1)
   7. B1
   8. B1
   9. BH
   10. GP
   11. B2
   12. BH
   13. GP
   14. B4
   15. BH
   16. GP
   17. B5
   18. B1
   19. B1
   20. B1
   21. B1
   22. B1
   23. BH
   24. B2
   25. BH
   26. GP
   27. B3
   28. BH
   29. GP