Carnegie MellonIntroduction to Computer Systems15-213/18-243, spring 200921stLecture, Apr. 2ndInstructors:Gregory Kesden and Markus PüschelCarnegie MellonAnnouncements Exam Next Tuesday Covers: Ch 5–8, 10.1–10.8 Next recitations: answering your questions Malloclab Due April 16th 150 points Can be done in teams of 2 (recommended to reduce workload) Has a check pointCarnegie MellonToday Memory related bugs System level I/O Unix I/O Standard I/O RIO (robust I/O) package Conclusions and examplesCarnegie MellonMemory-Related Perils and Pitfalls Dereferencing bad pointers Reading uninitialized memory Overwriting memory Referencing nonexistent variables Freeing blocks multiple times Referencing freed blocks Failing to free blocksCarnegie MellonDereferencing Bad Pointers The classic scanf bugint val;...scanf(“%d”, val);Carnegie MellonReading Uninitialized Memory Assuming that heap data is initialized to zero/* return y = Ax */int *matvec(int **A, int *x) { int *y = malloc(N*sizeof(int));int i, j;for (i=0; i<N; i++)for (j=0; j<N; j++)y[i] += A[i][j]*x[j];return y;}Carnegie MellonOverwriting Memory Allocating the (possibly) wrong sized objectint **p;p = malloc(N*sizeof(int));for (i=0; i<N; i++) {p[i] = malloc(M*sizeof(int));}Carnegie MellonOverwriting Memory Not checking the max string size Basis for classic buffer overflow attacks 1988 Internet worm Modern attacks on Web servers AOL/Microsoft IM warchar s[8];int i;gets(s); /* reads “123456789” from stdin */Carnegie MellonOverwriting Memory Misunderstanding pointer arithmeticint *search(int *p, int val) {while (*p && *p != val)p += sizeof(int);return p;}Carnegie MellonReferencing Nonexistent Variables Forgetting that local variables disappear when a function returnsint *foo () {int val;return &val;}Carnegie MellonFreeing Blocks Multiple Times Nasty!x = malloc(N*sizeof(int));<manipulate x>free(x);y = malloc(M*sizeof(int));<manipulate y>free(x);Carnegie MellonReferencing Freed Blocks Evil! x = malloc(N*sizeof(int));<manipulate x>free(x);...y = malloc(M*sizeof(int));for (i=0; i<M; i++)y[i] = x[i]++;Carnegie MellonFailing to Free Blocks (Memory Leaks) Slow, long-term killer! foo() {int *x = malloc(N*sizeof(int));...return;}Carnegie MellonFailing to Free Blocks (Memory Leaks) Freeing only part of a data structurestruct list {int val;struct list *next;};foo() {struct list *head = malloc(sizeof(struct list));head->val = 0;head->next = NULL;<create and manipulate the rest of the list>...free(head);return;}Carnegie MellonDealing With Memory Bugs Conventional debugger (gdb) Good for finding bad pointer dereferences Hard to detect the other memory bugs Debugging malloc (UToronto CSRI malloc) Wrapper around conventional malloc Detects memory bugs at malloc and free boundaries Memory overwrites that corrupt heap structures Some instances of freeing blocks multiple times Memory leaks Cannot detect all memory bugs Overwrites into the middle of allocated blocks Freeing block twice that has been reallocated in the interim Referencing freed blocksCarnegie MellonDealing With Memory Bugs (cont.) Some malloc implementations contain checking code Linux glibc malloc: setenv MALLOC_CHECK_ 2 FreeBSD: setenv MALLOC_OPTIONS AJR Binary translator: valgrind (Linux), Purify Powerful debugging and analysis technique Rewrites text section of executable object file Can detect all errors as debugging malloc Can also check each individual reference at runtime Bad pointers Overwriting Referencing outside of allocated block Garbage collection (Boehm-Weiser Conservative GC) Let the system free blocks instead of the programmer.Carnegie MellonOverwriting Memory Referencing a pointer instead of the object it points toint *BinheapDelete(int **binheap, int *size) {int *packet;packet = binheap[0];binheap[0] = binheap[*size - 1];*size--;Heapify(binheap, *size, 0);return(packet);}Carnegie MellonToday Memory related bugs System level I/O Unix I/O Standard I/O RIO (robust I/O) package Conclusions and examplesCarnegie MellonUnix Files A Unix file is a sequence of m bytes: B0, B1, .... , Bk, .... , Bm-1 All I/O devices are represented as files: /dev/sda2 (/usr disk partition) /dev/tty2 (terminal) Even the kernel is represented as a file: /dev/kmem (kernel memory image) /proc (kernel data structures)Carnegie MellonUnix File Types Regular file File containing user/app data (binary, text, whatever) OS does not know anything about the format other than “sequence of bytes”, akin to main memory Directory file A file that contains the names and locations of other files Character special and block special files Terminals (character special) and disks (block special) FIFO (named pipe) A file type used for inter-process communication Socket A file type used for network communication between processesCarnegie MellonUnix I/O Key Features Elegant mapping of files to devices allows kernel to export simple interface called Unix I/O Important idea: All input and output is handled in a consistent and uniform way Basic Unix I/O operations (system calls): Opening and closing files open()and close() Reading and writing a file read() and write() Changing the current file position (seek) indicates next offset into file to read or write lseek()B0B1• • • Bk-1BkBk+1• • •Current file position = kCarnegie MellonOpening Files Opening a file informs the kernel that you are getting ready to access that file Returns a small identifying integer file descriptor fd == -1 indicates that an error occurred Each process created by a Unix shell begins life with three open files associated with a terminal: 0: standard input 1: standard output 2: standard errorint fd; /* file descriptor */if ((fd = open("/etc/hosts", O_RDONLY)) < 0) {perror("open");exit(1);}Carnegie MellonClosing Files Closing a file informs the kernel that you are finished accessing that file Closing an already closed file is a recipe for disaster in threaded programs (more on this later) Moral: Always check return codes, even for seemingly benign functions such as close()int fd; /* file descriptor */int retval; /* return value */if ((retval = close(fd)) < 0) {perror("close");exit(1);}Carnegie
View Full Document