Course notes are available from here.

Scribe Notes

Courses/Computer_Science/CPSC_355.W2014/Lecture Notes/Scribe

(if you scribe a class session, your lowest homework grade will be upgraded a letter grade)

Week 1: Introduction

January 8: Overview

Courses/Computer_Science/CPSC_355.W2014/Lecture Notes/Overview

January 10: What is a Computer?

Courses/Computer_Science/CPSC_355.W2014/Lecture Notes/WhatIsComputer

Week 2: Architecture Overview, Computer Organization

This week, we will examine the main concepts involved in computer organization: in other words, the general design principles along which a digital calculation device might be organized and constructed.

A glance at the overall translation of C to x86 and SPARC assembly. Producing and examining assembly language. Producing and examining the ELF object file (a preview of week N).

Readings

A Tiny Guide to Programming in 32-bit x86 Assembly Language (you don't need to absorb this 100% right now, but skim through it for a summary of major IA-32 architectural features.
K&R: Chapter 1 (A Tutorial Introduction to C)
Paul: Chapter 1:
- 1.1 Introduction
- 1.2 Calculators
- 1.4 von Neumann
- 1.5 The Stack Machine
- 1.6 The JVM
- 1.7 Accumulator Machines
- 1.8 Load/Store Machines
- 1.9 Assemblers
- 1.10 Summary

January 13: Elements of The ISA

Courses/Computer_Science/CPSC_355.W2014/Lecture Notes/ISAIntro

January 15: Translation of C to ASM

Courses/Computer_Science/CPSC_355.W2014/Lecture Notes/IntroC2ASM

January 17: Instruction Semantics, Examining Program Execution

This week was really a teaser for the rest of the semester: you saw the most important "details" of the ISA (its major components and how they operate) as well as the process of translating C code into x86 assembly and machine code.

Courses/Computer_Science/CPSC_355.W2014/Lecture Notes/IA32Intro

Week 3: Digital Logic, Binary Numbers

Readings

K&R:
- Chapter 2 (Types)
- Chapter 3 (Control Flow)
Paul: Chapter 3, especially:
- 3.1
- 3.2
- 3.3
- 3.5

January 20: Binary and Hexadecimal Number Systems

prev. week was a teaser: you saw
- the architecture high level organization
- the process of turning source into assembly

Today we covered the basics of the binary and hexadecimal number systems. We looked at some basic boolean formulas to see the utility of binary in digital devices.

Now we need to go back and look at the fundamental underpinnings of all this: number systems and digital logic

January 22: Programming Meets Binary and Hex

We will see how x=x+1 can be implemented in assembly

Outline:

sanity check
class starter puzzles (review binary and hex)
octal in a nutshell
program x = x + 1, run in gdb
- demonstrates translation (again)
- demonstrates using gdb (again)
- highlights use of hex numbers in source and ASM
hand-executing x86 ASM activity

January 24: Translation From C to x86 Assembly

We spent the start of today reminding ourselves of how addition is supported by a circuit implementing logical operations. We then looked at a specific and simple piece of C code and saw how parts of it correspond to assembly-level code.

(eye@mordor l8)$ more add.c
int x = 0x1000; // 4096d
int main(int argc,

char* argv[])

{  
  x = x / 2;
  return x;
}
(eye@mordor l8)$

We compiled this add.c file to a file named a.out (the default name for an executable produced by gcc). This a.out file is an ELF executable, and the "file" command gives us more detail about it.

(eye@mordor l8)$ file a.out
a.out: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.18, not stripped
(eye@mordor l8)$

We can disassemble the resulting file with the objdump tool, asking it to display the output in Intel syntax and only disassemble the contents of the ELF ".text" section:

(eye@mordor l8)$ objdump -d -M intel -j ".text" a.out 
a.out:     file format elf32-i386
Disassembly of section .text:
080482e0 <_start>:
 80482e0:	31 ed                	xor    ebp,ebp
 80482e2:	5e                   	pop    esi
 80482e3:	89 e1                	mov    ecx,esp
 ...

Further down in this section is a symbol named "main", and this is where the code from our main function is placed by the compiler.

08048394 <main>:
 8048394:	55                   	push   ebp
 8048395:	89 e5                	mov    ebp,esp
 8048397:	a1 1c 96 04 08       	mov    eax,ds:0x804961c
 804839c:	89 c2                	mov    edx,eax
 804839e:	c1 ea 1f             	shr    edx,0x1f
 80483a1:	8d 04 02             	lea    eax,[edx+eax*1]
 80483a4:	d1 f8                	sar    eax,1
 80483a6:	a3 1c 96 04 08       	mov    ds:0x804961c,eax
 80483ab:	a1 1c 96 04 08       	mov    eax,ds:0x804961c
 80483b0:	5d                   	pop    ebp
 80483b1:	c3                   	ret    
 80483b2:	90                   	nop

We then tried to mentally match up the operations being performed here with our belief about what the source code was doing. A special note is that, although the C code is doing division, it is dividing by a number that we can treat specially at the assembly level (2). Dividing by two is equivalent to shifting a binary number right by 1 bit. The "shr, lea, sar" sequence performs this division of the global variable "x" (after first moving it into the eax (and then edx) registers from the memory location ds:0x804961c).

Week 4: Binary Arithmetic, Logic Operations

This week we will consider the foundational procedures for emulating basic mathematics and logical operations on numbers by their bit-level manipulation by hardware circuits.

Readings

Paul: Chapter 4, especially:
- 4.1: Intro
- 4.2: Binary Numbers and Addition
- 4.3: Half and Full Adders
- 4.4: Modulus Arithmetic
- 4.5: Subtraction
- 4.6: Two's Complement...
- 4.7: Unsigned Arithmetic
- 4.13: Summary

Optional:
- 4.8
- 4.9
- 4.10
- 4.11
- 4.12

January 27: Logical Implementation of ADD

Today we discussed how simple binary arithmetic could be implemented to support an ADD instruction in a machine instruction set. This functionality was based on modeling the process of addition as the combination of basic circuits and gates using AND, OR, and XOR.

January 29: Subtraction and Negative Numbers

Courses/Computer_Science/CPSC_355.W2014/Lecture Notes/SUBinx86

January 31: Instruction Implementation

Courses/Computer_Science/CPSC_355.W2014/Lecture Notes/InstrImpl

Week 5: Execution Artifact, Test

This week, we will take leave of our "foundational" knowledge of how many of the low-level details work and begin a more intense examination of the ABI and the execution artifact itself: the object code produced by a compiler and assembler that is eventually read and executed by a CPU.

Readings

K&R: Chapter 4 (Functions)
K&R: Chapter 5 (Pointers and Arrays)
Paul: Chapter 9 (External Text and Data)

February 3: Intro to ELF

Courses/Computer_Science/CPSC_355.W2014/Lecture Notes/ELFIntro

February 5: Midterm Exam

5 pages.

6 problems, mostly short answer.

100 points.

50 minutes.

No text.

No notes.

No calculator, computer, etc.

Write answers directly on the exam sheet.

Be prepared to write both C and ASM code.

February 7: ELF Continued

Courses/Computer_Science/CPSC_355.W2014/Lecture Notes/ELFCont

Week 6: Machine Instructions

This week we will examine the part of the ISA that defines the structure and semantics of machine instructions, paying particular attention to IA-32 in class; the readings will discuss SPARC, and we will cover SPARC in more detail in week 11.

Readings

Paul: Chapter 8 (Machine Instructions)

February 10: Machine Instruction Design Considerations

Courses/Computer_Science/CPSC_355.W2014/Lecture Notes/InstrFmt

February 12: Practice with Machine Instruction Decoding and Encoding

Courses/Computer_Science/CPSC_355.W2014/Lecture Notes/InstrEncoding

February 14: Pipelining

Courses/Computer_Science/CPSC_355.W2014/Lecture Notes/Pipeline

Week 7: Data Representation, Data Structures

This week we will examine how data structures (i.e., collections of primitive types) are represented to and manipulated by the CPU.

Readings

K&R: Chapter 6 (Structures)
Paul: Chapter 6 (Data Structures)

February 24: Primitive Types, Pointers

We started with an introduction of data types of c and the corresponding size requirements. char size is 1 byte, short size 2 bytes, int size is 4 bytes (should be atleast 2 bytes), long size is atleast 4 bytes (8 bytes for unix 64 bit system) and long long needs 64 bits or 8 bytes. We also discussed float and double data types. Float requires 4 bytes and double 8 bytes. We discussed the global variable declaration for these data types and how they are represented in .data section and the .bss section in assembly. .data section is used for declaring initialized data types and uninitialized variables go in .bss section. We examined the following c code to see how global variables are stored in .data and .bss sections

#include <stdio.h>
int x=3;
char ch= 'x';
float f=0.5;
long l;
int main(){
       char *ptr;
       int arr[10];
       struct str {
               int xy;
               int yz;
       };
       ptr = &ch;
       printf("size of pointer %lu\n", sizeof(ptr));
}

Disassembly shows that initialized data goes to .data section and unitialized to .bss section. Disassembly of section .data:

0000000000600890 <__data_start>:

 600890:	00 00                	add    %al,(%rax)

...

0000000000600894 <x>:

 600894:	03 00 00 00                                         ....

0000000000600898 <ch>:

 600898:	78 00 00 00                                         x...

000000000060089c <f>:

 60089c:	00 00 00 3f

Disassembly of section .bss:

00000000006008a0 <completed.6349>: ...

00000000006008a8 <dtor_idx.6351>: ...

00000000006008b0 <l>:

We also examined how contents are stored in the memory. First the lower bytes goes into the memory and then the high order bytes. We also examined the content differences between the float and int data types how these values are actually calculated. Then we discussed the sizeof operator of c which returns the size of any data type. We saw through the c code that how 'sizeof' keyword is used to calculate the size of various data types like int, char, arrays and structures (through simple examples). Then we discussed about the pointers. The size of pointer always returns the size of memory location regardless of the fact that whether it is a char pointer or an int pointer. It happens because pointer is actually a memory address. The sizeof keyword cannot be applied to incompletely defined data types.

February 26: Arrays, Structures, and Unions

Courses/Computer_Science/CPSC_355.W2014/Lecture Notes/ComplexTypes

February 28: Memory / Process Address Space

A discussion of global scope, local scope, dynamic memory.

static keyword

const keyword

Week 8: Control Flow

This week is an introduction to simple control flow constructs as represented in assembly. Simple direct branches and jumps; simple conditional branches. In each lecture, examine the running theme of the relationship with branches to the FDX cycle and pipelining.

Readings

K&R (read or re-read Chapter 4)
Paul: Chapter 7 (Subroutines)
7.1 -- 7.5

March 3: Basic Control Flow

Straightline Control Flow
Basic Blocks
Branches / Jumps
- Direct
- Indirect (e.g., via register)

March 5: Decision Control Structures

We will examine how if and case statements are implemented.

We will start, however, by looking at how control flow starts -- how does the function "main" actually get invoked?

test, compare, jump/condition
the Intel 8088 'J' family of instructions
consideration of the impact of branching on pipelines
drawing graphs of basic blocks (a simple program analysis technique)

Also:

notes, hints about course project
demo signup
future tutorials will be open work periods to work on the project or HW

March 7: Repetition Control Structures

We will examine how looping control is implemented.

Slides found here: http://pages.cpsc.ucalgary.ca/~rkumari/Repetition%20Control%20Flow.pdf

Week 9: Functions, Routines, Subroutines

This week is about advanced control flow. Simpler control flow topics we looked at included straightline assembly, simple branches between basic blocks, and simple conditional branching.

Code is often organized in an intermediate-sized code unit that includes several logically--related basic blocks; such routines often reflect a "function" or "method" in a procedural programming language. Different architectures define different protocols for invoking (i.e., jumping to) and returning from functions. Functions provide not only an independent code unit, but also a "separate" scratch memory area (often located on the program stack, and often not as separate as we'd like it to be for safe and reliable operation). This week, we will talk about a few different ways of supporting function invocation (such as activation records and register windows).

Readings

Paul: Chapter 7 (Subroutines)
7.6--7.11

March 10: Function-level Control Flow

rationale for functions / subroutines (structured control flow, naming, parameterization)
terminology: functions, procedures, routines, subroutines, methods
assembly instructions to support function/routine control flow, branching
setup of activation record on the x86

March 12: Activation Records

convention for calling functions
passing data, pointers, arguments
- AR format
- register windows
local variables
AR layout
arrays as local variables
arrays as parameters

March 14: Function Context

examine stack frame with gdb
memory management
- alloca
function pointers
inline functions
effects on the ISA
returning from functions
other types of routines (e.g., co-routines, recursion)

(eye@mordor functions)$ gdb -q ./px
Reading symbols from /home/eye/355/lectures/functions/px...done.
(gdb) break main
Breakpoint 1 at 0x8048430: file program.c, line 22.
(gdb) run
Starting program: /home/eye/355/lectures/functions/px 
Breakpoint 1, main (argc=1, argv=0xbffff9b4) at program.c:22
22	  int x = 0;
Missing separate debuginfos, use: debuginfo-install glibc-2.12-1.107.el6.i686
(gdb) bt full
#0  main (argc=1, argv=0xbffff9b4) at program.c:22
        x = 7622644
        c = "\203\004\b\213\204\004\b"
(gdb) x/32x $esp
0xbffff8e0:	0x007431e4	0x08048248	0x00745ce0	0x00744ff4
0xbffff8f0:	0x08048480	0x08048330	0x0804848b	0x00744ff4
0xbffff900:	0x08048480	0x00000000	0xbffff988	0x005c8ce6
0xbffff910:	0x00000001	0xbffff9b4	0xbffff9bc	0xb7fff3d0
0xbffff920:	0x08048330	0xffffffff	0x005aafc4	0x08048248
0xbffff930:	0x00000001	0xbffff970	0x0059aa05	0x005abab0
0xbffff940:	0xb7fff6b0	0x00744ff4	0x00000000	0x00000000
0xbffff950:	0xbffff988	0xf304662e	0xb5ef1151	0x00000000
(gdb) i r esp
esp            0xbffff8e0	0xbffff8e0
(gdb) disassemble 
Dump of assembler code for function main:
   0x08048427 <+0>:	push   ebp
   0x08048428 <+1>:	mov    ebp,esp
   0x0804842a <+3>:	and    esp,0xfffffff0
   0x0804842d <+6>:	sub    esp,0x20
=> 0x08048430 <+9>:	mov    DWORD PTR [esp+0x1c],0x0
   0x08048438 <+17>:	mov    DWORD PTR [esp+0x15],0x6c6c6568
   0x08048440 <+25>:	mov    WORD PTR [esp+0x19],0x6f
   0x08048447 <+32>:	mov    BYTE PTR [esp+0x1b],0x0
   0x0804844c <+37>:	mov    DWORD PTR [esp],0x1
   0x08048453 <+44>:	call   0x80483e4 <foo>
   0x08048458 <+49>:	mov    DWORD PTR [esp+0x1c],eax
   0x0804845c <+53>:	lea    eax,[esp+0x15]
   0x08048460 <+57>:	mov    DWORD PTR [esp],eax
   0x08048463 <+60>:	call   0x80483fc <bar>
   0x08048468 <+65>:	mov    eax,DWORD PTR [esp+0x1c]
   0x0804846c <+69>:	leave  
   0x0804846d <+70>:	ret    
End of assembler dump.
(gdb) nexti
23	  char c[7]="hello";
(gdb) disassemble 
Dump of assembler code for function main:
   0x08048427 <+0>:	push   ebp
   0x08048428 <+1>:	mov    ebp,esp
   0x0804842a <+3>:	and    esp,0xfffffff0
   0x0804842d <+6>:	sub    esp,0x20
   0x08048430 <+9>:	mov    DWORD PTR [esp+0x1c],0x0
=> 0x08048438 <+17>:	mov    DWORD PTR [esp+0x15],0x6c6c6568
   0x08048440 <+25>:	mov    WORD PTR [esp+0x19],0x6f
   0x08048447 <+32>:	mov    BYTE PTR [esp+0x1b],0x0
   0x0804844c <+37>:	mov    DWORD PTR [esp],0x1
   0x08048453 <+44>:	call   0x80483e4 <foo>
   0x08048458 <+49>:	mov    DWORD PTR [esp+0x1c],eax
   0x0804845c <+53>:	lea    eax,[esp+0x15]
   0x08048460 <+57>:	mov    DWORD PTR [esp],eax
   0x08048463 <+60>:	call   0x80483fc <bar>
   0x08048468 <+65>:	mov    eax,DWORD PTR [esp+0x1c]
   0x0804846c <+69>:	leave  
   0x0804846d <+70>:	ret    
End of assembler dump.
(gdb) x/32x $esp
0xbffff8e0:	0x007431e4	0x08048248	0x00745ce0	0x00744ff4
0xbffff8f0:	0x08048480	0x08048330	0x0804848b	0x00000000
0xbffff900:	0x08048480	0x00000000	0xbffff988	0x005c8ce6
0xbffff910:	0x00000001	0xbffff9b4	0xbffff9bc	0xb7fff3d0
0xbffff920:	0x08048330	0xffffffff	0x005aafc4	0x08048248
0xbffff930:	0x00000001	0xbffff970	0x0059aa05	0x005abab0
0xbffff940:	0xb7fff6b0	0x00744ff4	0x00000000	0x00000000
0xbffff950:	0xbffff988	0xf304662e	0xb5ef1151	0x00000000
(gdb) nexti
0x08048440	23	  char c[7]="hello";
(gdb) x/32x $esp
0xbffff8e0:	0x007431e4	0x08048248	0x00745ce0	0x00744ff4
0xbffff8f0:	0x08048480	0x6c656830	0x0804846c	0x00000000
0xbffff900:	0x08048480	0x00000000	0xbffff988	0x005c8ce6
0xbffff910:	0x00000001	0xbffff9b4	0xbffff9bc	0xb7fff3d0
0xbffff920:	0x08048330	0xffffffff	0x005aafc4	0x08048248
0xbffff930:	0x00000001	0xbffff970	0x0059aa05	0x005abab0
0xbffff940:	0xb7fff6b0	0x00744ff4	0x00000000	0x00000000
0xbffff950:	0xbffff988	0xf304662e	0xb5ef1151	0x00000000
(gdb) nexti
0x08048447	23	  char c[7]="hello";
(gdb) 
25	  x = foo(1);
(gdb) nexti
0x08048453	25	  x = foo(1);
(gdb) disassemble 
Dump of assembler code for function main:
   0x08048427 <+0>:	push   ebp
   0x08048428 <+1>:	mov    ebp,esp
   0x0804842a <+3>:	and    esp,0xfffffff0
   0x0804842d <+6>:	sub    esp,0x20
   0x08048430 <+9>:	mov    DWORD PTR [esp+0x1c],0x0
   0x08048438 <+17>:	mov    DWORD PTR [esp+0x15],0x6c6c6568
   0x08048440 <+25>:	mov    WORD PTR [esp+0x19],0x6f
   0x08048447 <+32>:	mov    BYTE PTR [esp+0x1b],0x0
   0x0804844c <+37>:	mov    DWORD PTR [esp],0x1
=> 0x08048453 <+44>:	call   0x80483e4 <foo>
   0x08048458 <+49>:	mov    DWORD PTR [esp+0x1c],eax
   0x0804845c <+53>:	lea    eax,[esp+0x15]
   0x08048460 <+57>:	mov    DWORD PTR [esp],eax
   0x08048463 <+60>:	call   0x80483fc <bar>
   0x08048468 <+65>:	mov    eax,DWORD PTR [esp+0x1c]
   0x0804846c <+69>:	leave  
   0x0804846d <+70>:	ret    
End of assembler dump.
(gdb) x/32x $esp
0xbffff8e0:	0x00000001	0x08048248	0x00745ce0	0x00744ff4
0xbffff8f0:	0x08048480	0x6c656830	0x00006f6c	0x00000000
0xbffff900:	0x08048480	0x00000000	0xbffff988	0x005c8ce6
0xbffff910:	0x00000001	0xbffff9b4	0xbffff9bc	0xb7fff3d0
0xbffff920:	0x08048330	0xffffffff	0x005aafc4	0x08048248
0xbffff930:	0x00000001	0xbffff970	0x0059aa05	0x005abab0
0xbffff940:	0xb7fff6b0	0x00744ff4	0x00000000	0x00000000
0xbffff950:	0xbffff988	0xf304662e	0xb5ef1151	0x00000000
(gdb) nexti
0x08048458	25	  x = foo(1);
(gdb) diassemble
Undefined command: "diassemble".  Try "help".
(gdb) disassemble
Dump of assembler code for function main:
   0x08048427 <+0>:	push   ebp
   0x08048428 <+1>:	mov    ebp,esp
   0x0804842a <+3>:	and    esp,0xfffffff0
   0x0804842d <+6>:	sub    esp,0x20
   0x08048430 <+9>:	mov    DWORD PTR [esp+0x1c],0x0
   0x08048438 <+17>:	mov    DWORD PTR [esp+0x15],0x6c6c6568
   0x08048440 <+25>:	mov    WORD PTR [esp+0x19],0x6f
   0x08048447 <+32>:	mov    BYTE PTR [esp+0x1b],0x0
    0x0804844c <+37>:	mov    DWORD PTR [esp],0x1
   0x08048453 <+44>:	call   0x80483e4 <foo>
=> 0x08048458 <+49>:	mov    DWORD PTR [esp+0x1c],eax
   0x0804845c <+53>:	lea    eax,[esp+0x15]
   0x08048460 <+57>:	mov    DWORD PTR [esp],eax
   0x08048463 <+60>:	call   0x80483fc <bar>
   0x08048468 <+65>:	mov    eax,DWORD PTR [esp+0x1c]
   0x0804846c <+69>:	leave  
   0x0804846d <+70>:	ret    
End of assembler dump.
(gdb) i r esp
esp            0xbffff8e0	0xbffff8e0
(gdb) x/32x $esp
0xbffff8e0:	0x00000001	0x08048248	0x00745ce0	0x00744ff4
0xbffff8f0:	0x08048480	0x6c656830	0x00006f6c	0x00000000
0xbffff900:	0x08048480	0x00000000	0xbffff988	0x005c8ce6
0xbffff910:	0x00000001	0xbffff9b4	0xbffff9bc	0xb7fff3d0
0xbffff920:	0x08048330	0xffffffff	0x005aafc4	0x08048248
0xbffff930:	0x00000001	0xbffff970	0x0059aa05	0x005abab0
0xbffff940:	0xb7fff6b0	0x00744ff4	0x00000000	0x00000000
0xbffff950:	0xbffff988	0xf304662e	0xb5ef1151	0x00000000
(gdb) break bar
Breakpoint 2 at 0x8048402: file program.c, line 16.
(gdb) cont
Continuing. 
Breakpoint 2, bar (c=0xbffff8f5 "hello") at program.c:16
16	  fprintf(stdout, "%c\n", c[0]);
(gdb) disassemble
Dump of assembler code for function bar:
   0x080483fc <+0>:	push   ebp
   0x080483fd <+1>:	mov    ebp,esp
   0x080483ff <+3>:	sub    esp,0x18
=> 0x08048402 <+6>:	mov    eax,DWORD PTR [ebp+0x8]
   0x08048405 <+9>:	movzx  eax,BYTE PTR [eax]
   0x08048408 <+12>:	movsx  ecx,al
   0x0804840b <+15>:	mov    edx,0x8048534
   0x08048410 <+20>:	mov    eax,ds:0x80496e0
   0x08048415 <+25>:	mov    DWORD PTR [esp+0x8],ecx
   0x08048419 <+29>:	mov    DWORD PTR [esp+0x4],edx
   0x0804841d <+33>:	mov    DWORD PTR [esp],eax
   0x08048420 <+36>:	call   0x8048318 <fprintf@plt>
   0x08048425 <+41>:	leave  
   0x08048426 <+42>:	ret    
End of assembler dump.
(gdb) i r esp
esp            0xbffff8c0	0xbffff8c0
(gdb) x/32x $esp
0xbffff8c0:	0xbffff960	0x080496b8	0xbffff8d8	0x080482e4
0xbffff8d0:	0x00000005	0x2816f198	0xbffff908	0x08048468
0xbffff8e0:	0xbffff8f5	0x08048248	0x00745ce0	0x00744ff4
0xbffff8f0:	0x08048480	0x6c656830	0x00006f6c	0x2816f198
0xbffff900:	0x08048480	0x00000000	0xbffff988	0x005c8ce6
0xbffff910:	0x00000001	0xbffff9b4	0xbffff9bc	0xb7fff3d0
0xbffff920:	0x08048330	0xffffffff	0x005aafc4	0x08048248
0xbffff930:	0x00000001	0xbffff970	0x0059aa05	0x005abab0
(gdb) x/32x $ebp
0xbffff8d8:	0xbffff908	0x08048468	0xbffff8f5	0x08048248
0xbffff8e8:	0x00745ce0	0x00744ff4	0x08048480	0x6c656830
0xbffff8f8:	0x00006f6c	0x2816f198	0x08048480	0x00000000
0xbffff908:	0xbffff988	0x005c8ce6	0x00000001	0xbffff9b4
0xbffff918:	0xbffff9bc	0xb7fff3d0	0x08048330	0xffffffff
0xbffff928:	0x005aafc4	0x08048248	0x00000001	0xbffff970
0xbffff938:	0x0059aa05	0x005abab0	0xb7fff6b0	0x00744ff4
0xbffff948:	0x00000000	0x00000000	0xbffff988	0xf304662e
(gdb) bt full
#0  bar (c=0xbffff8f5 "hello") at program.c:16
No locals.
#1  0x08048468 in main (argc=1, argv=0xbffff9b4) at program.c:27
        x = 672592280
        c = "hello\000"
(gdb)

Week 10: External Data and Text, Execution Support / ABI

Assembly programs, particularly for RISC-style architectures, usually operate on data in registers (i.e., small storage elements located in the CPU itself and defined by the ISA). Programs typically use more than this finite amount of storage, so the ISA and ABI must provide a way for programs to access a larger memory -- including the ability to map in the code and data from other libraries needed by the program.

We will continue our consideration of how programs are able to use more than just statically allocated primitive types. We will pay particular attention to the heap and the program stack, an area of dynamic memory typically used to store data needed by functions and subroutines. We will also examine the DOS and Linux system call interfaces.

the ldd command
pmap (see shared libraries)
static compilation vs. dynamic binary

Readings

Paul: Chapter 5 (The Stack)
Paul: re-read Chapter 9

March 17: The Process Address Space

An overview of the concept, structure, and content of the process address space. This space is an enumerable array of memory for storing both program code and many types of program data, some of which is determined at compile/assembly time and some of which is dynamically created at load time and during runtime.

(eye@mordor ~)$ ps aux | grep yes
eye       6023  5.0  0.0   4068   492 pts/15   S+   09:45   0:00 yes hello
eye       6028  0.0  0.0   4356   740 pts/16   S+   09:45   0:00 grep yes
(eye@mordor ~)$ cat /proc/6023/maps
0058c000-005aa000 r-xp 00000000 08:03 404092     /lib/ld-2.12.so
005aa000-005ab000 r--p 0001d000 08:03 404092     /lib/ld-2.12.so
005ab000-005ac000 rw-p 0001e000 08:03 404092     /lib/ld-2.12.so
005b2000-00742000 r-xp 00000000 08:03 404104     /lib/libc-2.12.so
00742000-00743000 ---p 00190000 08:03 404104     /lib/libc-2.12.so
00743000-00745000 r--p 00190000 08:03 404104     /lib/libc-2.12.so
00745000-00746000 rw-p 00192000 08:03 404104     /lib/libc-2.12.so
00746000-00749000 rw-p 00000000 00:00 0 
00fda000-00fdb000 r-xp 00000000 00:00 0          [vdso]
08048000-0804d000 r-xp 00000000 08:03 27448      /usr/bin/yes
0804d000-0804f000 rw-p 00004000 08:03 27448      /usr/bin/yes
092f1000-09312000 rw-p 00000000 00:00 0          [heap]
b74ff000-b76ff000 r--p 00000000 08:03 6972       /usr/lib/locale/locale-archive
b76ff000-b7700000 rw-p 00000000 00:00 0 
b770d000-b770f000 rw-p 00000000 00:00 0 
bfb62000-bfb77000 rw-p 00000000 00:00 0          [stack]
(eye@mordor ~)$

March 19: Where Does Data Live?

We have already discussed the distinction between global data and data local to a function. The central question is "what is enforcing the semantics of the keywords we use without a second thought at the source level?" In some cases, this is the compiler...in other cases the architecture (such as an illegal memory reference)...in other cases, the OS is doing so.

Concepts

Compilation units.
The static keyword.
The const keyword.
The extern keyword.

Code

"combined" main.c
main.c
foo.c
bar.c
baz.c

We dealt with two "problems" emerging from splitting up the original main.c into four distinct translation units.

The declaration of 'foo' as a static function (and thus not visible to main() in main.c)
The need for foo.c, bar.c, and baz.c to "see" the symbol 'x'.

(eye@mordor sep)$ make
gcc -Wall -c foo.c
foo.c: In function ‘foo’:
foo.c:3: error: ‘x’ undeclared (first use in this function)
foo.c:3: error: (Each undeclared identifier is reported only once
foo.c:3: error: for each function it appears in.)
make: *** [foo] Error 1
(eye@mordor sep)$

Now that the error with the missing 'int x' declaration is dealt with in foo.c, the compiler complains about 'foo()' being defined but never used (and that is the case, b/c foo() is still static and never called from any other translation unit. The compiler then also complains about the use of the undefined symbol 'x' in bar.c.

(eye@mordor sep)$ make
gcc -Wall -c foo.c
foo.c:3: warning: ‘foo’ defined but not used
gcc -Wall -c bar.c
bar.c: In function ‘bar’:
bar.c:5: error: ‘x’ undeclared (first use in this function)
bar.c:5: error: (Each undeclared identifier is reported only once
bar.c:5: error: for each function it appears in.)
make: *** [bar] Error 1
(eye@mordor sep)$

We then encounter an interesting problem, which is that main.c needs function declarations of foo(), bar(), and baz() before the linker can resolve these symbols.

(eye@mordor sep)$ make
gcc -Wall -c foo.c
foo.c:3: warning: ‘foo’ defined but not used
gcc -Wall -c bar.c
gcc -Wall -c baz.c
gcc -Wall -o mx main.c foo.o bar.o baz.o
main.c: In function ‘main’:
main.c:17: warning: implicit declaration of function ‘foo’
main.c:19: warning: implicit declaration of function ‘bar’
main.c:25: warning: implicit declaration of function ‘baz’
/tmp/ccojGXG9.o: In function `main':
main.c:(.text+0x12): undefined reference to `foo'
collect2: ld returned 1 exit status
make: *** [main] Error 1
(eye@mordor sep)$ emacs -nw main.c

When we fixed that second problem by including a declaration of 'int x' in each of those three files, we wondered why we didn't need to use the 'extern' keyword, as the program seems to work correctly:

(eye@mordor sep)$ make
gcc -Wall -c foo.c
gcc -Wall -c bar.c
gcc -Wall -c baz.c
gcc -Wall -o mx main.c foo.o bar.o baz.o
(eye@mordor sep)$ ./mx
ret of bar is 33
ret of bar is 33
ret of baz is 1
ret of baz is 3

See next class notes for the answer.

Announcements

HW5 hints and tips re: dynamic memory
Join the USENIX Association as a student member
Test cases (many are looking good!) (worth 10% of your grade on the project)
Volunteer for 502 project participants
Structure of Demo

March 21: Asking the System for "External" Resources

The primary lesson from today is that programs written in a high-level languages depend not only on the semantics and behavior of the machine instructions and features of the ISA, but also the "execution environment", including operating system services (e.g., system calls) and the structure and content of the process address space.

Increasing the heap. Asking mmap for an anonymous private memory mapping. Loading shared libraries.

Memory
- mmap
Libraries
- ldd
- ld
  - static binary vs. dynamically-linked binary
  - ld.so
  - LD_PRELOAD
- dlopen, dlclose, dlsym, dlerror

Notes

Finish up discussion of global symbol 'x' from Wednesday.

The reason that the program works is given in K&R, Appendix A, S10.2 and 11.2 (extern visibility, and linkage). The declarations of 'x' are considered temporary until the compiler encounters a definition (such as an initialization of x in main.c or baz.c) of that variable.

(eye@mordor sep)$ nm foo.o
00000000 T foo
00000004 C x
(eye@mordor sep)$ nm bar.o
00000000 T bar
00000000 D x
(eye@mordor sep)$ nm baz.o
00000000 T baz
00000000 b j.1236
00000004 C x
(eye@mordor sep)$ nm mx
...
080484b8 T bar
080484dc T baz
...
080484a4 T foo
...
080497ac b j.1236
080483e4 T main
...
080485d4 R try_writing_to_this
08049798 D x

We see that the global variable x has been placed at address 0x8049798, and that the references to it from the other compilation units are rewritten by the linker to use that address. There is not need for the extern keyword in this case. We can see that the machine code in foo.o is using the offset zero to represent the "declared but not defined" variable 'x'

(eye@mordor sep)$ objdump -d -M intel foo.o
foo.o:     file format elf32-i386
Disassembly of section .text:
00000000 <foo>:
   0:	55                   	push   ebp
   1:	89 e5                	mov    ebp,esp
   3:	a1 00 00 00 00       	mov    eax,ds:0x0
   8:	01 c0                	add    eax,eax
   a:	a3 00 00 00 00       	mov    ds:0x0,eax
   f:	90                   	nop
  10:	5d                   	pop    ebp
  11:	c3                   	ret    
(eye@mordor sep)$

Consulting the 'nm' manual pages, we see that the 'C' designator in the nm output for those three object files means:

          "C" The symbol is common.  Common symbols are uninitialized data.
              When linking, multiple common symbols may appear with the same
              name.  If the symbol is defined anywhere, the common symbols
              are treated as undefined references.

When the symbol 'x' is finally defined, it is assigned a virtual address, placed in the .data section, and has the "D" designator associated with it in nm's output (see above). From the nm man page:

          "D"
          "d" The symbol is in the initialized data section.

Static and dynamic linking.
Stripping symbols.

Week 11: SPARC Case Study

Throughout this week, we will consider the basic elements of the SPARC ISA, compare them with the Intel x86, consider what they teach us about the RISC philosophy, and seek to understand the relationship and constraints between SPARC, the compiler, and the programmer.

Readings

Paul: Chapter 2 (SPARC Architecture)

March 24: Overview of SPARC ISA

March 26: SPARC Instruction Format, Instruction Set

RISC-style ISAs often have the distinctive feature of having a fixed, well-defined instruction length (e.g., all instructions are 32 bits). They also tend to have a large number of general purpose registers and several other features that express themselves in the instruction format. Today we will take a closer look at the SPARC instruction format to illustrate some of these features and compare them against the variable length instructions present in 8086/8088 (and x86 generally).

March 28: Branching in SPARC

A consideration of routine-level control flow, and the effect of branching on pipelined execution

NB: this topic was deferred in favor of discussion of how to structure your assembler.

Week 12: Assembler Design Issues

March 31: Approach to Parsing

April 2: Basics of Translation

April 4: Advanced Pipeline Concepts (+USRI)

superscalar
- ULTRA SPARC
- Intel NetBurst

USRI survey (last 20 minutes of class)

Week 13: Advanced Issues

April 7: Advanced Arch Features

Today we'll discuss some of the "advanced" features of the Intel IA-32. These features lay the groundwork for interesting systems support like threading (i.e., concurrency), OS support, fine-grained timing (e.g., for perf. measurement), other performance tuning, and support for true random number generation.

Continue discussion of superscalar, out of order execution, speculative execution, etc.
Hyperthreading
other System registers (control registers, debug registers, etc.)
Interesting instructions
- cpuid
- random number generation
- rdtsc

other topics

Branch prediction
LOCK
virtualization support

Notes/Links

April 9: I/O

x86 i/o instructions
- I/O addressing
- I/O registers
traps, interrupts
memory mapped I/O, character I/O, programmed I/O

Themes:

Interrupts vs. polling
Synchronous vs. asynchronous
complex reality of microarchitectures hidden underneath "public" ISA

Readings

Read Chapter 10 in SPARC text
http://zsmith.co/intel_o.html#out
http://zsmith.co/intel_i.html#in
data sheet
Intel IA-32 developer manual, Volume 1, Chapter 16: Input/Output (5 printed pages)
Intel IA-32 developer manual, Volume 2, 3-394 Vol. 2A "IN—Input from Port", pdf page 456
- notes on implementation, specifically as regards privilege level checks and I/O permissions map sub-check

Example:

IN (fixed, hard-coded port as 8 bit immediate value): 1110010w port
IN (variable port, placed in DX by programmer):       1110110w 
IN AX, 0x60
IN AX, DX

April 11: I/O In Action

Smoke on the Water

http://courses.engr.illinois.edu/ece390/books/labmanual/io-devices-speaker.html
- question: what do the control signal numbers mean?
- answer: see "cod3b453"'s response: http://board.flatassembler.net/topic.php?t=14711

Misc

Week 13: Flex

April 14: BSD (no class)

BSD. No class today.

Final project due at 11:59pm.

Courses/Computer Science/CPSC 355.W2014/Lecture Notes

Contents

Scribe Notes

Week 1: Introduction

January 8: Overview

January 10: What is a Computer?

Week 2: Architecture Overview, Computer Organization

January 13: Elements of The ISA

January 15: Translation of C to ASM

January 17: Instruction Semantics, Examining Program Execution

Week 3: Digital Logic, Binary Numbers

January 20: Binary and Hexadecimal Number Systems

January 22: Programming Meets Binary and Hex

January 24: Translation From C to x86 Assembly

Week 4: Binary Arithmetic, Logic Operations

January 27: Logical Implementation of ADD

January 29: Subtraction and Negative Numbers

January 31: Instruction Implementation

Week 5: Execution Artifact, Test

February 3: Intro to ELF

February 5: Midterm Exam

February 7: ELF Continued

Week 6: Machine Instructions

February 10: Machine Instruction Design Considerations

February 12: Practice with Machine Instruction Decoding and Encoding

February 14: Pipelining

Week 7: Data Representation, Data Structures

February 24: Primitive Types, Pointers

February 26: Arrays, Structures, and Unions

February 28: Memory / Process Address Space

Week 8: Control Flow

March 3: Basic Control Flow

March 5: Decision Control Structures

March 7: Repetition Control Structures

Week 9: Functions, Routines, Subroutines

March 10: Function-level Control Flow

March 12: Activation Records

March 14: Function Context

Week 10: External Data and Text, Execution Support / ABI

March 17: The Process Address Space

March 19: Where Does Data Live?

March 21: Asking the System for "External" Resources

Week 11: SPARC Case Study

March 24: Overview of SPARC ISA

March 26: SPARC Instruction Format, Instruction Set

March 28: Branching in SPARC

Week 12: Assembler Design Issues

March 31: Approach to Parsing

April 2: Basics of Translation

April 4: Advanced Pipeline Concepts (+USRI)

Week 13: Advanced Issues

April 7: Advanced Arch Features

April 9: I/O

April 11: I/O In Action

Week 13: Flex

April 14: BSD (no class)

Navigation menu

Search