administrivia

• hw1 out tomorrow, due in two weeks—start early!
• access to dropbox
• how many went to 8:30 last Thursday?
• ex0/1 grades
• pointers
  • sections this Thursday; self-exercises
  • google for “C pointer exercises” and do as many as you can
• function calls
  • CSE 351, lec 6, “procedures & stacks”
  • CSE 351’s bufbomb or MIT 6.033’s buffer overrun hands-on

feedback

• anonymous: upload section slides w/ valgrind/makefile
  • sections slides are available on the course website
  • check out hw0, or talk to us
• export slides to pdf
• never saw big-endian (PowerPC) computers
  • Apple iBook & PowerBook
  • Xbox 360, Wii & Wii U, PlayStation 3
  • Curiosity (Mars rover), Deep Blue (vs. Kasparov), …
  • emulator

Curiosity Mars rover

casting vs. endianness

#include <inttypes.h>
#include <stdio.h>
#include <string.h>
int main(void)
{
    uint16_t x = 0xbeef;
    uint8_t a, b;

    a = (uint8_t)x;
    b = *(uint8_t *)&x;

    printf("%" PRIx8 " %" PRIx8 "\n", a, b);
}

today’s plan

• review CSE 351, lec 11, “memory allocation”
• overview: static, automatic, and dynamic allocation
• C memory allocators

why dynamic memory allocation

• suppose we want to
  • read a 4-byte integer n from network
  • continue to read n bytes
  • n is not known in advance
• suppose we want to
  • load the content of a file into memory
  • the file size is not known in advance

malloc

void *
malloc(size_t n);

• request
  • I’d like to reserve a virtual address range of n bytes
  • I don’t care about the start address
• return ptr
  • virtual address range [ptr, ptr + n) is now yours
  • the content is uninitialized; write to the range before read
  • free the range when you don’t need it anymore
• return NULL
  • out of memory: you’d better have a plan or just panic

free

void
free(void *ptr);

• request
  • take back the virtual address range starting from ptr
  • I’m not telling you the size; figure that out yourself
• I promise
  • ptr is a return value from malloc/calloc/realloc
  • ptr has never been freed before
  • I’m not going to use the range after this point
• see also: calloc, realloc

example (partly from CSE 351)

/* allocate a block of n ints: [0, n-1] */
int *foo(size_t n) {
    size_t i;
    int *p = malloc(n * sizeof(int));
    if (p == NULL)
        return NULL;
    for (i = 0; i < n; i++)
        p[i] = i;
    return p;
}
void bar(size_t n) {
    int *p = foo(n);
    ...
    free(p);
}

what if n is a very large integer?

self-exercise: malloc_array

/**
 * malloc_array - allocate memory for an array.
 *  n:    number of elements.
 *  size: element size.
 */
void *malloc_array(size_t n, size_t size)
{
    ???
    return malloc(n * size);
}

assume the maximum value of size_t is SIZE_MAX

see also: kmalloc_array, reallocarray, and dlcalloc

static/automatic/dynamic alloc

#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
char gvar[128];
int main(void) {
    char buf[64];
    void *ptr = malloc(32);

    printf("gvar: %p\n", gvar);
    printf("buf:  %p\n", buf);
    printf("ptr:  %p\n", ptr);

    printf("main: %p\n\n", main);
    snprintf(buf, sizeof(buf), "cat /proc/%d/maps", getpid());
    return system(buf);
}

lifetime of gvar, buf, and ptr?

lifetime

can overflow happen?

see Toyota unintended acceleration lawsuit

memory allocators

• malloc & free
  • good control
  • unsafe and hard to use: leak, use-after-free, double free
  • valgrind is your friend
  • performance: glibc’s malloc vs Google’s tcmalloc
  • security: OpenBSD’s malloc and more defenses
• other memory management schemes

garbage collection

• example: libgc/Boehm GC

• easy to use
  • just call malloc()
  • no need to call free() anymore
  • fewer bugs

• less control: unpredictable pause

reference counting

examples: Objective-C, file descriptors, C++’s shared_ptr

NSArray *arr = [ [ NSArray alloc ] init ]; // counter: 1
[arr retain];                              // counter: 2
[arr release];                             // counter: 1
[arr release];                             // counter: 0, freed

• each object has a counter, initially 1
• retain: counter incremented by 1
• release: counter decremented by 1
• freed when counter reaches 0

regions (pools)

examples: Apache web server, Subversion

apr_pool_t *pool;
apr_pool_create(&pool, NULL);
...
char *buf = apr_palloc(pool, 128);
long *arr = apr_palloc(pool, sizeof(long) * 10);
...
apr_pool_destroy(pool);

• apr_palloc(pool, n): allocate n bytes from pool
• apr_pool_destroy(pool): free the entire pool
• no individual free

self-exercise

write and test a program that defines:

• a new struct type Point
  • represent it with floats for the x, y coordinate
• a new struct type Rectangle
  • assume its sides are parallel to the x-axis and y-axis
  • represent it with the bottom-left and top-right Points
• a function that computes/returns the area of a Rectangle
• a function that tests whether a Point is in a Rectangle

see solution

self-exercise

typedef struct complex_st {
    double real; // real component
    double imag; // imaginary component
} Complex;

typedef struct complex_set_st {
    int num_points_in_set;
    Complex *points; // an array of Complex
} ComplexSet;

ComplexSet *AllocSet(Complex c_arr[], int size) { ... }
void FreeSet(ComplexSet *set) { ... }

AllocSet needs to use malloc twice: to allocate a ComplexSet, and to allocate points inside it; FreeSet needs to use free twice

see solution

see you on Wednesday

• review CSE 351, lec 7, “arrays & structs” (including typedef)
• next lecture: data structures