2009-11-18

Post date: Nov 23, 2009 8:02:31 PM

    • Why isn't stack allocation enough for programming?
      • Stack-allocated objects become invalid as soon as the function returns, so callee cannot return objects on stack back to the caller.
      • Caller can create an object on stack and pass its pointer to the callee to store results there, but the caller must be able to predict how much space will be used by the callee (e.g. gettimeofday(), strftime(), fgets(), snprintf(), ...) Typically, the callee return value has a special way to indicate whether the space provided by the caller was sufficient.
      • Not a good paradigm for data structure, even those as simple as a list. The functions to enumerate directory entries for example---opendir(), readdir(), closedir()---are awkward to use and error prone if used incorrectly.
    • What is the heap?
      • Traditional Unix process views the heap as an extension to the data section, in order to store additional "global" objects created in run time. The data section typically stores objects created as a global variable.
      • Heap is grown in opposite direction to the stack (see figure on the right).
      • The brk() system call sets the end of the data section; sbrk() is a wrapper that remembers and returns the previous end of the data section, and adjusts the new end by the given number of bytes. In other words, use of sbrk() feels like malloc().
      • There is no corresponding free() for the data section. The end of the data section can be shrunk, but one must take the trouble to ensure that the shrinkage does not cause objects that are still in use to be invalidated.
      • brk() typically operates on one page at a time: if we want 8 bytes, it will still give us a page (4096 bytes). We typically use malloc(), which obtains memory from sbrk(), to manage the heap in a fine grained way.
      • Modern operating systems use paged virtual memory management to allocate pages anywhere in the address space.
    • Simple strategies to manage the heap:
      • Use it like a stack. The decoupling of call stack and object stack means objects can survive the scope of a function call. Objects must be freed in the exact opposite order they're allocated. See K&R section 5.4 pp. 101.
      • Use a singly linked list to chain free memory blocks. Objects may be freed in any order. May cause fragmentation problem. See K&R section 8.7 pp. 185.
    • A word about using union (see K&R pp. 147) for alignment: K&R pp. 186 presents this object header definition:
      • typedef long Align; /* for alignment to long boundary */ union header { /* block header: */ struct { union header *ptr; /* next block if on free list */ unsigned size; /* size of this block */ } s; Align x; /* for alignment of blocks */ }; typedef union header Header;
      • The use of union in this case ensures that header is at least as big as the Align type, which is typedef as a long int. The malloc() code on pp. 187 uses sizeof(Header) to round up the number of bytes to allocate.
        • On a 16-bit machine, long int is 4 bytes, pointer 2 bytes, and unsigned int 2 bytes. The union does nothing in this case because sizeof(x) == sizeof(s) (x and s are the members in the union).
        • On a 32-bit machine, long int is 4 bytes, pointer 4 bytes, and unsigned int 4 bytes. All of them are aligned to their size. The union does nothing in this case because sizeof(x) < sizeof(s).
        • On a 64-bit machine, long int is 8 bytes, pointer 8 bytes, and unsigned int 4 bytes. The struct is 12 bytes, and the union still does nothing because sizeof(x) < sizeof(s).
      • In all cases, sizeof(Header) == sizeof(s), so the union does nothing. Furthermore, on 64-bit machine, the compiler may leave sizeof(Header) as 12 bytes, which is not a very good number to round up to.