CMPSC 311 Exam2 - abutalib aghayev PDF

Preview

Summary

abutalib aghayev...

Description

Memory Management Box and arrow diagrams

Double pointers

Pointer Arithmetic •

Pointers are typed o int *int_ptr; vs. char *char_ptr; o pointer arithmetic obeys those types o i.e. when you add 1 to pointer, you add sizeof() that type

Buffer • • • •

memory region that has some use typically is referenced (maintained) through pointer char *buffer; temporary holding place void buffers o general purpose pointer (pointer to raw address) o there is no data type for this, thus compiler has no idea what this pointing to ▪ use casting to coerce type for use

Copying memory •

memcpy copies one memory region to another o copy from “source” buffer to “destination” buffer o size must be explicit (because there is no terminator) o 𝑚𝑒𝑚𝑐𝑝𝑦(𝑑𝑒𝑠𝑡, 𝑠𝑟𝑐, 𝑛) is kinda like 𝑑𝑒𝑠𝑡 = 𝑠𝑟𝑐

Memory comparison • • •

We often want to compare buffers to see if they match or are byte-wise smaller or larger memcmp compares first n bytes of buffers mcmcmp(buf1, buf2, n) comparison functions return o negative integer if buf1 is less than buf2 0 if buf1 is equal to buf2 o positive integer if buf1 greater than buf2

Filling memory •

memset fills memory with given constant byte o void *memset(void *buf, int c, size_t n)

Memory allocation •

counter is statically allocated o allocated when program is loaded o deallocated when program exits

•

a, x, y are automatically allocated o allocated when function is called o deallocated when function returns

Dynamic allocation •

• • •

dynamically allocated memory o program explicitly requests new block of memory, language runtime allocates it , perhaps with help from OS dynamically allocated memory persists until: o code explicitly deallocates it [manual memory management] garbage collector collects it [automatic memory management] C require you to manually manage memory o Gives you more control, but causes headaches o C has no garbage collection

Garbage collection • • • •

In some languages like Java, you can dynamically allocate objects using built in “new” function of Java runtime environment Stays in memory until invisible process (garbage collection) behind scenes frees o Typically done in background by background process Pros: large class of memory bugs avoided o Dereferencing dangling pointers, memory leaks, double freeing of memory, … Cons: unpredictable memory o Garbage collection can start at arbitrary time and slow down program

C and malloc •

malloc allocates block of memory of given size void *malloc(size_t size) o returns void pointer to first byte of that memory o no need to cast – void pointer is automatically promoted ▪ malloc returns NULL if memory could not be allocated o should assume memory initially contains garage o typically use sizeof to calculate size you need o Linux overcommits memory by default, malloc never fails

C and calloc •

Similar to malloc, but zeros out allocated memory void *calloc(size_t nmemb, size_t bytes); o Returns array of nmemb members, each of size bytes o Memory is zeroed out (all bytes have value 0x0) o Slightly slower; preferred for non-performance-critical code o malloc and calloc are found in stdlib.h

Deallocation •

• •

release memory pointed-to by pointer o pointer must point to first byte of heap-allocated memory ▪ i.e., something previously returned by malloc() or calloc() o after free()ing block of memory, that block memory might be returned in some future malloc()/calloc() it’s good form to set pointer to NULL after freeing it otherwise we pointer can malloc() and free() structs, as with other types

Realloc (re-allocation) •

realloc changes previous allocation (resizing it) o resize previous allocation in place, if possible o if it can’t, it creates new allocation and copies as much data as it can o returns NULL if memory could not be allocated

Heap •

•

heap (aka “free store”) – large pool of unused memory that is used for dynamically allocated data o malloc allocates chunks of data in heap, free deallocates data o malloc maintains book-keeping data in heap to track allocated blocks malloc and friends are ordinary functions in standard C library (or libc)

Null •

guaranteed-to-be-invalid memory location o in C on Linux: Null is 0x00000000 o attempt to deference NULL causes segmentation fault o that’s why you should NULL pointer after you have free()d it ▪ it’s better to have segfault than to corrupt memory

Memory corruption

Memory leak – happens when code fails to deallocate dynamically allocated memory that will no longer be used Implications of leak •

program’s virtual memory will keep growing o for short-lived programs, this might be OK o for long-lived programs, this usually has bad repercussions ▪ might slow down over time (VM thrashing)

• potential “DoS attack” if server leaks memory ▪ might exhaust all available memory and crash ▪ other programs might get starved at memory o in some cases, you might prefer to leak memory than to corrupt memory with buggy free() AddressSanitizer is built into your compiler •

gcc -fsanitize = address foo.c -o foo

Virtual memory •

top of heap is program break o program heap gets moved up and down as memory is allocated and deallocated heap

brk() and sbrk() •

functions are used to manage program break o void *brk(void *ptr) – changes new program break to address of ptr ▪ absolute pointer, so very dangerous o void *sbrk(int inc) – moves program break inc (increment) bytes upward or downward ▪ positive inc allocates new memory ▪ negative inc frees memory

Alternative allocation •

some implementations of malloc don’t use program break, but uses alternate method that “memory maps” region and size to allocate blocks of memory from o memory maps – tells OS that range of memory should be available for use by program o can be anywhere in process (i.e. it ignores program break) o implementation of malloc and free use memory mapping instead… ▪ mmap() instead of brk()/sbrk() ▪ munmap() instead of brk()/sbrk() o it is matter of design which variable we use

OS Paging •

• • •

Programs have virtual address space o OS fetches data from either physical memory or disk o Done by mechanism called (demand) paging Divide virtual address space into units called “virtual pages” each of which is of fixed size (usually 4k or 8k) Physical address partitioned into “physical pages” / “frames” OS traces virtual pages in physical memory

o Maintained in data structure called “page-table” o “Page-tables” map Virtual-to-Physical addresses Pointers & Arrays Multidimensional Array Layout • • •

•

Arrays are laid out in row-major order int x[2][4] = {{1, 2, 3, 4}, {5, 6, 7, 8}} int x[3][2][7] = {{1, 2, 3, 4}, {5, 6, 7, 8}}, {{9, 10, 11, 12}, {13, 14, 15, 16}}, {{17, 18, 19, 20}, {21, 22, 23, 24}}} Multidimensional arrays must have bounds for all dimensions except first o Following are okay: int[][4] = …; int [][2][4] = …; o Given expression x[1][2], we need length of second row to compute offset

Arrays of Strings

Command-line arguments • • •

•

So far, out main functions was accepting no (void) parameters o int main (void) {…} We can access command-line arguments using following parameters: o int main (int argc, char *argv[]) {…} Since arrays decay into pointers, following is OK too: o int main (int argc, char *argv) {…} "*" in type "char **" is used to indicate that the type is pointer to pointer to char, it's not the "*"

• •

operator that dereferences a pointer. In the printf statement, the "char **" type variable "p" is dereferenced once, and the "*p" is of type "char *" which represents the string. Since "argv" has starting address of an array of "char *" type pointers, variable holding the starting address is a pointer to "char *" type, resulting in "char **". When you have an array of "char" that's a string, the variable holding the starting address of that string is of type "char *" pointer to char. Similarly, when you have an array of "char *" that's an array of strings, the variable holding the starting address of that array is of type "char **", pointer to pointer to char.

Pointers to Pointers •

We already know how to modify non-pointer variables through functions: o We pass address to function, i.e. we pass pointers to variables int x = 1, y = 2; void swap (int *x, int *y) { int tmp = *x; *x = *y; *y = tmp; }; o Modify pointer variable itself int x = 1, y = 2; *xp = &x; *yp = &y; void swapception (int **xp, int **yp) {int *tmp = *xp; *xp = *yp; *yp = tmp}; o Why? Data Structures (linked lists, trees, etc.)

Strings in C •

•

String is just array o C handles ASCII text through strings: nullterminated array characters o There are large number of interfaces for managing strings available in C library, i.e., string.h How strings are stored in memory o String literals are in read-only region of memory o Arrays (char x[]) are initialized by compiler ▪ Contents copied from string in read-only region o Pointers (char *x) points directly to read-only region

sizeof vs strlen o sizeof(string) returns size of declaration (sometimes, beware) o strlen(string) returns length of string, not including null terminator Initializing strings – bad strings have no null terminator called unterminated string Copying strings o strcpy (dest, src) – copies src to dest up and including null-terminator

n – variants of string functions o best way to thwart buffer overflows (and generally make more safe code) is to use “n” variants of string functions (i.e., you can copy string to make it more safe) strncpy(dest, src, n) o Warning: if sources does not have NULL terminator in first n bytes, “dest” will not be terminated Concatenating Strings o In C, we use strcat (which appends src to dest) strcat(dest, src); o strncat variant copies at most n bytes of src strncat(dest, src, n);

String comparison o Compare string to see if they match or are lexicographically smaller or larger o In C, we use strcmp (which compares s1 to s2) strcmp(s1, s2); o strncmp compares first n bytes of strings strncmp(s1, s2, n); o Comparison functions return o Negative integer if s1 is less than s2 o 0 if s1 is equal to s2 o Positive integer if s1 greater than s2 Searching strings

o Searching through strings to find something we are looking for: o strchr searches front to back for character o strrchr searches back to front for character strchr(str, char_to_find); strrchar(str, char_to_find); o strstr searches front to back for string o strcasestr searches from front for string (ignoring case) o All these functions return pointer within string to found value of NULL if not found

Parsing strings o String carry information we want to translate (parse) into other (variables) o In C, we use sscanf which extract data by format sscanf(str, “format”, …); o Syntax is very similar to that of printf, but your arguments must be passed by reference o Returns number of arguments successfully parsed

File Input / Output Input / Output o Process of moving bytes into and out of devices, files, networks, etc. o Terminal / keyboard (terminal I/O) o Secondary storage (file I/O) o Network (network I/O) o Different I/O types require different interfaces o Terminal I/O is messy Buffered vs. Unbuffered

o When system is buffering o It may read more than requested in expectation you will read more later (read buffering) o It may not commit all bytes to target (write buffering) Blocking vs. Nonblocking vs. Asynchronous o Non-blocking I/O o Call does not wait for read or write to complete before returning o Thus read/write may commit / return some, all, or none of data requested o When fewer than request bytes are read / written – short read or short write o Asynchronous I/O o Use different API than blocking / non-blocking I/O o I/O request return immediately o Callback is generated when I/O completes o How you program I/O operations is dependent on blocking behavior of I/O you are using Terminal o Three default terminal channels: STDIN, STOUT, STDERR o UNIX commands / programs for terminal output o echo – prints out formatted output to terminal STDOUT (e.g., echo “hello world”) o cat – prints out file (or STDIN) contents to STDOUT (e.g., cat mdadm.c) o less – provides read-only view for input (or file) (e.g., less mdadm.c) IO Redirection o Redirection uses file for inputs, outputs, or both o Output redirection sends output of program to file (redirects to file) (echo “cmpsc311 output redirection” > this.dat) o Input redirection uses contents of file as program input (redirects from file) (cat < this.dat) o You can do both at same time (cat < this.dat > out.dat)

Pipes o Pipe take output from one program and uses it as output for another o cat this.dat | less ( = less this.dat) o cat this.dat > x less < x o Can also chain pipes together o cat number.txt | sort -n | cat libc – standard library for C programming language contains code and interfaces we use for basic program operation and interact with parent operating system; basic interfaces: o o o o o o o

stdio.h – declarations for input/output stdlib.h – declarations for misc system interfaces stdint.h – declarations for basic integer data types signal.h – declaration for OS signals and functions math.h – declarations for many useful math functions time.h – declarations for basic time handling functions … many, many, more

Library call vs. system call o Difference between open and fopen o open is system call ▪ open() system call opens file specified by pathname. If specified file does not exist, it may optionally (if O_CREAT is specified in flags) be created by open() o fopen is library call ▪ fopen() function opens file whose name is string pointed to by pathname and associates stream with it man man o System calls, library calls, etc., have their own sections

o Use “man 3 fopen” to read manual page of fopen library call o Will see references such as “foo(2)” or “bar(3)” o Number in parenthesis refer to manual page section, implies call type File IO – provides random access to file within filesystem: o With specific “path” (location of file) o At any point in time it has location pointer in file next read and writes will begin at that position o All file I/O works in following way o Open file o Read/write contents o Close file Locating files for IO o Absolute path fully specifies directories and filename itself from filesystem root “/” /home/mcdaniel/courses/cmpsc311 -sum19/this.dat o Relative path – directories and filename from (or relative to) current directory o ./courses/cmpsc311/ -sum19/this.dat ▪ . = current directory ▪ ./ = starting from current directory o courses/cmpsc311/ -sum19/this.dat o All of these references refer to same file FILE* based IO o One of basic ways to manage input and output is use FILE set of functions provided by libc o FILE structure is data structure created to manage input and output for file o Abstraction of “high level” file I/O that avoids some of details of programming o Almost always used for reading and writing ASCII data o fopen returns FILE o FILE = structure fopen()

o fopen function open file for IO and returns pointer to FILE* structure: FILE *fopen (const char *path, const char *mode); o Where, o path – string containing absolute or relative path to file to be opened o mode – string describing ways file will be used o For example, FILE *file = fopen(filename, “r+”); o Returns pointer to FILE* if successful, NULL otherwise ▪ You don’t have to allocate or deallocate FILE* structure o FILE* structure is referred to as stream fopen modes o “r” – open text file for reading; stream is positioned at beginning of file o “r+” – open for reading and writing; stream is positioned at beginning of file o “w” – truncate file to zero length or create text file for writing. Stream is positioned at beginning of file o “w+” – open for reading and writing file is created if it does not exist, otherwise it is truncated o “a” – open for appending (writing at end of file); file is created if it does not exist o “a+” – open for reading and appending (writing at end of file); file is created if it does not exist Reading file o fscanf reads data from file just like scanf, just reading and writing o fscanf = scan formatted o fgets read line of text from file Writing file o fprintf writes data to file just like printf, just reading and writing o fputs writes line of text to file

fflush o FILE* - based IO is buffered o fflush attempts to reset / flush state int fflush (FILE *stream); o FILE* - based writes are buffered, so there may be data written, but not yet pushed to OS ▪ fflush() forces writes of all buffered data o FILE* - based reads are buffered, so current data (in process space) may not be current ▪ fflush() discards buffered data from underlying file o If stream argument is NULL, flush() flushes all open output streams o fflush() does not guarantee that data is safely on disk; for that use fsync(2) o one advantage of using fopen over open is that fopen does automatic buffering o When we use the library call fopen(), fprintf(), fputs() and so on, we are actually writing to the buffer in the user space. fflush()keep the buffer in the kernel space up to date by moving the data in the user space buffer to kernel space. Also fclose() call fflush() implicitly. The reason for buffering is because system calls are expensive. We don't want to use system call for each fprintf(). And to keep the data on the disk up to date, we will use fsync(). fclose() o closes file and releases memory associated with FILE* structure o fclose() implicitly flushes data to OS

open() o open system calls open file for IO and returns integer file handle: int open (const char *path, int flags, mode_t mode); o Where, o path – string containing absolute or relative path to file to be opened o flags indicate kind of open you are requesting o mode sets security policy for file o open() returns “file handle” open() flags o “flags” to open with o O_RDONLY – read only o O_WRONLY – write only o O_RDWR – read and write o Options o O_CREAT – if file does not exist it will be created o O_EXCL – ensure that call creates file, fail otherwise (fail if already exists) o O_TRUNC – if file already exists it will be truncated to length 0 Access Control in UNIX o UNIX filesystem implements discretionary access control through file permission set by user

o Permission are set at discretion of user o Every file in file system has set bits which determine who has access to files o User – owner is typically creator of file, and entity in control of access control policy o Group – set of users on system setup by admin o World – set of everyone on system o This can be override by “root” user UNIX filesystem rights o READ – allows subject (process) to read contents of file o WRITE – allows subject (process) to alter contents of file o EXECUTE – allows subject (process) to execute contents of file (e.g., shell, program, executable, …) UNIX Access Policy

o Policy is encoded as “r”, “w”, “x” if enabled, and “-“ if not, e.g., rwxrw---x Says users can read, write, and execute, group can read and write, and world can execute only

File descriptor – index assigned by kernel into table of file information maintained in OS o File descriptor table is unique to each process and contains details of open files o File descriptors are used to reference when calling I/O system calls o Kernel accesses file for process and returns results in system call response Reading and Writing o Primitive reading and writing mechanism that only process only blocks of opaque data ssize_t write (int fd, con...