Lecture Notes for Computer Algorithms I

28 October 2003 - Case Study: Manual Memory Management

The Problem

• Reading HTTP messages from the network is hard.

  • Messages arrive in pieces.

  • Message size is often implicit.

  $ ./word-counter -d13 >/dev/null                                 
  Open client socket 6.
  read(6) returned 2180.
  host = www.monmouth.edu, port = 80
  Open server connection 8.
  write(8) returned 2180.
  read(8) returned 1460.
  read(8) returned 1460.
  read(8) returned 5840.
  read(8) returned 5851.
  write(6) returned 14611.
  read(8) returned 0.
  Close socket 8.
  Close socket 6.
  

The Solution

• Read from the network into a fixed-size buffer.

  const unsigned bsize = 10000;
  char buffer[bsize];
  int e = read(skt, buffer, bsize);
  

  • The network protocol (TCP/IP) buffers unread data.

  • Repeated reads eventually get all the data.

• Store from the fixed-size buffer into a variable-sized buffer.

  • A resource is a good data structure for this.

    • data points to the buffer.

    • size gives the amount of data in the buffer.

  • Extend resource to include the buffer size.

    • And a way to add data to the buffer.

The Implementation

• Resource was extended to http-message to include the buffer size and append().

  void http_message::
  append(ccp dt, unsigned sz)
  
    if (size + sz >= size_max)
      size_max *= 2
  
      char * ndata = new char [size_max]
      memcpy(ndata, data, size)
      delete [] data
      data = ndata
  
    memcpy(data + size, dt, sz)
    size += sz
  

• append() doubles size to increase buffer space.

  • It results in a log number of re-allocations.

  • The STL vector uses this approach, for example.

  • Unfortunately, this problem isn't like an STL vector.

The Problem

• word-counter coredumps sometimes.

  $ ./word-counter -d13 > /dev/null
  Open client socket 6.
  read(6) returned 2180.
  Segmentation Fault(coredump)
  
  $ gdb word-counter core
  GNU gdb 5.2
  (gdb) up
  165    char * buffer = new char[sz + 1];
  (gdb) list 161, 166
  161  bool match(ccp start, ccp end) {
  162     
  163    assert(start <= end);
  164    const unsigned sz = end - start;
  165    char * buffer = new char[sz + 1];
  166    memcpy(buffer, start, sz);
  (gdb) print sz
  $1 = 2180
  (gdb) 
  
  

  • And sometimes only on certain systems.

  • www.monmouth.edu coredumped on rockhopper, but not on cslab.

A Clue

• Compare and contrast.

  cslab (from lynx)
  $ ./word-counter -d13 >/dev/null Open client socket 6. read(6) returned 2180. host = www.monmouth.edu, port = 80 Open server connection 8. write(8) returned 2180. read(8) returned 1460. read(8) returned 1460. read(8) returned 5840. read(8) returned 5851. write(6) returned 14611. read(8) returned 0. Close socket 8. Close socket 6.
  rockhopper (from firebird)
  $ ./word-counter -d13 > /dev/null Open client socket 4. read(4) returned 474. host = www.monmouth.edu, port = 80 Open server connection 5. write(5) returned 474. read(5) returned 2896. read(5) returned 10000. Memory fault (core dumped)

The Fix

• Doubling size is fine if you're adding one extra element.

• Resize size_max properly.

• Check the size assumptions.

  void http_message::
  append(ccp dt, unsigned sz)
  
    if (size + sz >= size_max)
      size_max *= 2
      size_max = 2*(size + sz)
  
      char * ndata = new char [size_max]
      memcpy(ndata, data, size)
      delete [] data
      data = ndata
  
    assert(size + sz <= size_max)
    memcpy(data + size, dt, sz)
    size += sz
  

Right vs. Wrong

• There are many ways to go wrong, but few ways to go right.

  • It's more likely you'll be wrong rather than right.

• Check to make sure you're right.

  assert(size + sz <= size_max)
  memcpy(data + size, dt, sz)
  
  $ ./word-counter > /dev/null 
  word-counter: http-message.cc:26: 
  http_message::append(char*, unsigned): 
  Assertion size + sz <= size_max failed.
  Abort (core dumped) 
  

• Had I done this initially, I would have saved myself

  • A few weeks of on-and-off debugging.

  • The public embarrassment of non-working code.

Points to Remember

• Manual memory management is difficult and unforgiving.

  • Make absolutely sure you need to do it.

• Keep manual memory management short and simple.

  • Unfortunately, c++ makes this hard to do.

• Manual memory mismanagement can lead to baffling and obscure errors.

  • Usually long ago and far away from the problem.

• Verify your assumptions.

  • Know what your assumptions are.

• Manual memory management is difficult and unforgiving.

  • Make absolutely sure you need to do it.

This page last modified on 28 October 2003.