MOP Midterm 2 - Linux/C Programming/Heap operations, MOP Midterm 2 - Assembly Language and ISA, MOP Midterm 2 - Memory Heirarchy/Cache

What is shadowing?

when a local variable has the same name as another variable in the same scope thus hiding the non local variable (should and can be avoided!)

What is the POSIX API?

The portable OS interface standard for maintaining compatibility among Unix OS, whose functions are accessible with unistd.h

What is unistd.h?

A collection of OS functions (system call wrappers) used to access functions in the POSIX API. Some of these functions like brk() and sbrk() can be used to implement your own heap allocator.

What is brk?

"program break" - pointer to end of program and top of heap

What does brk() do?

brk(void *addr) OS function that sets top of heap to passed address.

**OS initially clears new pages of heap memory for security

What is errno?

Set by OS functions to communicate a specific error to program code. Error number can be interpreted with strerror(errno)

What does strerror() do?

strerror(errno) returns a description of the error associated with errno

What will happen if you use the OS functions brk() or sbrk() along with malloc(), calloc(), and free()?

Undefined program behavior

What does sbrk() do?

sbrk(intptr_t incr) OS function that takes an int (that is implicitly converted to intptr_t so it can be added to a pointer) size to (+) or (-) the size of the heap by incr bytes.

What is stdlib.h?

It is the standard library for C programming. It contains functions that allow for conversion, execution flow, math, search, sorting, and randoms

What do atoi() and atol() do?

Converts ascii (string/char array) to an integer/long respectively

What's the difference between atol() and strtol()

atol(char* str) can only convert from base 10 and always returns 0 if the parse is impossible

strtol(char str, char* endptr, int base) can convert any number from base 2 to 36 and on failure can give location where parse ended by changing the value of the passed pointer and an error if the number is too big or small

What is bsearch()?

A standard library function that conducts a binary search

What is qsort()?

A standard library function that implements the quick sort algorithm

What is a *void?

A generic pointer

What is the difference between calloc and malloc?

calloc populates all returned heap space with 0s and takes two arguments (numElements, sizeofElement), whereas malloc doesn't modify contents heap space before allocation and takes one argument (numBytes)

**Note calloc is much slower because it clears the data to 0s

What does realloc() do?

realloc(numElements, elementSize) resizes a previously allocated block of memory and returns a new pointer

What is a heap block?

A chunk of contiguous memory with overhead and payload

What is overhead?

Data/Padding that takes up extra heap space from payload data.

May contain a pointer to the next block if the allocator uses a linked list

What is payload?

The part of a block that holds the data stored there that is used by the process

What is the allocator?

A program that allocates, frees, splits, and coalesces heap blocks

What is the difference between an implicit and explicit allocator?

An implicit allocator uses a "new" operator to determine number of bytes needed, and the garbage collector automatically frees unused heap memory

An explicit allocator requires the user to manually allocate and free heap memory

What are the two goals in allocator design?

Maximize throughput - # of malloc and free requests allocator can satisfy (measured in O(n))

Maximize Memory Utilization - % of memory used for payload (more payload bytes, less overhead)

**INCREASING ONE DECREASES THE OTHER GENERALLY

What are the requirements of a heap allocator?

1. Provide immediate response

2. Handle any sequence of malloc and free requests

3. Can't move allocated blocks

4. Must follow memory alignment requirements

What are the two requirement of double word alignment?

1. Block SIZE and payload ADDRESS must be a multiple of double word length (usually 8)

What is external fragmentation?

total memory space exists to satisfy a request, but it is not contiguous

What is internal fragmentation?

allocated memory may be slightly larger than requested memory; this size difference is memory internal to a partition, but not being used

Why doesn't Java allow primitives on the heap?

Because primitives are very small in size (1-4 bytes), so a lot of padding is required for the memory alignment requirements; Too much internal fragmentation

What is the difference between explicit and implicit free list?

Explicit utilizes a data structure to store the location and size of free blocks.

Implicit store size and status within heap blocks in overhead as headers/footers

What is explicit free list organization?

- When free block location and size are stored in an unordered data structure (like an array of structs with a pointer and int each) by allocator. This list can be separate from or integrated into the heap

- programmer only needs to keep trace of block size (all free blocks are in the data structure)

- More memory is needed to store free list, but time is faster because only free blocks are searched

What is implicit free list organization?

When headers (first word) are used to store size and status of block, and headers are used so allocator can have info about previous block

-Programmer must track block size and status

-Can use less memory than explicit list

-Long search time because every block must be checked

How are the last 3 bits of the size of a block able to be used to store additional information?

Because the block size must be a multiple of 8, so last three bits are always 0.

What are heap placement policies?

Strategies used to determine which free heap block to use to satisfy a request

What are the different placement policies?

First fit - starts at beginning of heap and allocates first block found

Next fit - starts from most recently allocated block and allocates first block found

Best fit - runs through entire heap and allocates the block closest to desired block size

Why does the first fit policy have good memory utilization?

Likely to choose block close to desired size because smaller blocks are at the start of the heap

Pros and cons of block splitting by allocator?

( + ) Better memory utilization, less overhead

( - ) Worse throughput, more blocks = more jumps = slower search

What's the difference between immediate and delayed coalescing?

Immediate coalescing will coalesce any adjacent blocks after freeing a block of at all possible

Delayed coalescing will only coalesce when there is a need for it

Why don't allocated blocks need footers?

Footers are only used for coalescing

What is false fragmentation?

When two contiguous blocks of memory have enough space to satisfy a request but can't because they are separate blocks

How can you integrate an explicit free list into the heap?

By adding extra overhead to free blocks as predecessor and successor pointers. This increases minimum block size.

Does the order of free blocks in the free list need to be the same order as they are found in the address space?

No

What's the difference between EFL address ordering and last-in ordering?

Address ordering orders blocks from low to high address in EFL (better memory utilization malloc() w/ FF policy)

Last-in ordering puts most recently freed block to front of EFL (better free() performance cuz no sorting)

What's the difference between EFL simple segregation and fitted segregation

-Simple segregation has a separate EFL for each block size, so size headers are necessary, just successor pointers.

-Fitted segregation uses size ranges rather than specific sizes.

How does simple EFL segregation work?

-Different EFL for each block size

-headers aren't necessary, block just needs successor pointer

-Fast malloc and free

-If corresponding list is empty, search larger lists or request more memory from OS

***Causes more fragmentation of both types because no splitting or coalescing

What is free list segregation?

When the heap allocator uses an array of free lists segregated by block size to organize free blocks

How does fitted EFL segregation work?

-Free Blocks are segregated into different EFLs for different size ranges (small, medium, large)

-allows for better throughput as only some free blocks need to checked

-Uses FF searching through range, if nothing found go to larger range and split block

Why don't conse

What is ISA?

Instruction Set Architecture, like IA-32

What is machine code?

This is low-level binary code that represents how computer hardware and CPUs understand instructions. It is specific to different machines!

How long is an IA-32 instruction?

1-15 bytes

T/F Memory bits do not distinguish instructions from different data types from pointers

True, the only way the machine knows what kind of info it's getting is from how memory is accessed (instruction fetching or operant loading) and from the operation and operands of the instruction itself

How does word size differ between caching and assembly?

4 bytes in cache, 2 bytes in assembly

How does IA-32 machine code see a C char?

byte (b)

How does IA-32 machine code see a C int?

Double word (l) 4 bytes

How does IA-32 machine code see a C char*? (All ptrs)

Double word (l) 4 bytes

How much data can IA-32 registers store?

1, 2, and 4 bytes of data or a 4 byte address

%eax

Accumulator register for arithmetic operations.

%ecx

Counter - counting and loops

%edx

data - stores data

%ebx

base - stores base value/address

%esi

source index -

%edi

Destination Index -

%esp

Stack pointer register indicating top of stack.

%ebp

Base pointer - points to base of stack

Which two registers used for stack bounds?

esp and ebp, they are only used to store the start and end of the stack

%eip

Program Counter (extended instruction pointer)

What does the program counter do?

Holds the address of the next instruction to be fetched. This address is obtained while the current instruction is executed

What are condition code registers?

(AKA e-flags) 1 bit registers whose bits are automatically set to store status of the most recent ALU operation for conditional execution

What are operand specifiers?

S and D, S specifies the location of value to be used by an instruction and D specifies location where result is to be stored. They come in the form of different ways of formatting operands to show how the machine should interpret them.

What does the $ operand specifier represent?

A constant value rather than a location

How do you use a hex number as a constant in assembly?

$0xBEEFBABE

What does the % operand specifier represent?

Specifies an operand value that is in a register

What is an effective address?

An operand to an instruction that references memory, sometimes given indirectly

What is absolute addressing mode?

Imm - A numerical value with no specifiers. The operand is located at the memory location corresponding to the numerical value

How is the effective address obtained in indirect addressing mode?

- The effective address of the operand is found in the register

How do you know what size specifier to use when you only know the one of the operands?

Since that operand will be a register/constant, use its size as the size specifier

What are all the 8 bit registers in the 32 bit system?

ah-dh & al-dl

What are all the 16 bit registers in the 32 bit system?

ax-dx, si, di, sp, bp

What addressing mode is this: (%Reg)

indirect addressing

How is the effective address obtain in base + offset mode?

The effective address is found by adding the offset to the address in the given register

What addressing mode is this: Imm(%Reg)

base+offset

How is the effective address obtained in indexed addressing mode?

- Effective address is obtained by adding values contained in index and base register

What addressing mode is this: (%BaseReg,%IndexReg)

indexed addressing mode

What addressing mode is this: Imm(%Reg,%Reg)

Indexed + offset addressing mode

How is the effective address obtain in indexed + offset addressing mode?

- Effective address is obtained by adding values contained in index and base register plus the offset

What addressing mode is this: Imm(%Reg,%Reg,s)

Base + scaled index + offset

How is the effective address obtained in Base + scaled index + offset addressing mode

- Effective address is obtained by adding value contained at the base register to the result of scaling the value in the index register, then add the offset

What addressing mode is this:

(%Reg,%Reg,s)

Scaled index no offset

What addressing mode is this:

Imm(,%Reg,s)

Scaled index no base

What addressing mode is this:

(,%Reg,s)

Scaled index no base no offset

What does the % operand specifier represent?

A register

What size can base registers be

Only 32 - bit

What values can scale factor be?

Only 1,2,4, or 8

What do the instruction Mov, PUSH, and POP do?

Copy data from source to destination to allow data to move around memory and registers

How does MOV work?

MOV S,D - Copies S to D

**S and D must be of equal size

How do Movz and Movs work?

MOV[Z/S][b/w/l][b/w/l] S,D allow for copying data when S and D are different sizes. MOVZ fills the remain space with 0s and MOVS sign extends to fill the rest of the space

How does pushl work?

pushl S allows for a double word to be copied onto top of stack.

**Note that storing data on the stack requires it first be grown by subtracting from stack pointer: R[%esp] <- R[%esp] - sizeof(S)

M[R[%esp]] <- S

How does popl work?

popl D allows for double word at the top of the stack to be copied from the stack

**Note that removing data on the stack requires it be shrank by adding to stack pointer after data is copied:

M[R[%esp]] -> D

R[%esp] <- R[%esp] + sizeof(D)

Which way does the stack grow?

Down to lower memory addresses.

Which way does the heap grow?

UP towards the Stack