title: Critique my non-intrusive heap debugger
body: <p>This is a follow-up to <a href="https://stackoverflow.com/questions/2830272/critique-my-heap-debugger">Critique my heap debugger</a> from yesterday. As suggested by bitc, I now keep metadata about the allocated blocks in a separate handwritten hashtable.</p>
  
  <p>The heap debugger now detects the following kinds of errors:</p>
  
  <ol>
  <li>memory leaks (now with more verbose debugging output)</li>
  <li>illegal pointers passed to delete (that also takes care of double deletes)</li>
  <li>wrong form of delete (array vs. non-array)</li>
  <li>buffer overflows</li>
  <li>buffer underflows</li>
  </ol>
  
  <p>Feel free to discuss and thanks in advance!</p>
  
  <pre><code>#include &lt;cstdio&gt;
  #include &lt;cstdlib&gt;
  #include &lt;cstring&gt;
  #include &lt;new&gt;
  
  namespace
  {
      // I don't want to #include &lt;algorithm&gt; for a single function template :)
      template &lt;typename T&gt;
      void my_swap(T&amp; x, T&amp; y)
      {
          T z(x);
          x = y;
          y = z;
      }
  
      typedef unsigned char byte;
  
      const byte CANARY[] = {0x5A, 0xFE, 0x6A, 0x8D,
                             0x5A, 0xFE, 0x6A, 0x8D,
                             0x5A, 0xFE, 0x6A, 0x8D,
                             0x5A, 0xFE, 0x6A, 0x8D};
  
      bool canary_dead(const byte* cage)
      {
          bool dead = memcmp(cage, CANARY, sizeof CANARY);
          if (dead)
          {
              for (size_t i = 0; i &lt; sizeof CANARY; ++i)
              {
                  byte b = cage[i];
                  printf(b == CANARY[i] ? "__ " : "%2X ", b);
              }
              putchar('\n');
          }
          return dead;
      }
  
      enum kind_of_memory {AVAILABLE, TOMBSTONE, NON_ARRAY_MEMORY, ARRAY_MEMORY};
  
      const char* kind_string[] = {0, 0, "non-array memory", "    array memory"};
  
      struct metadata
      {
          byte* address;
          size_t size;
          kind_of_memory kind;
  
          bool in_use() const
          {
              return kind &amp; 2;
          }
  
          void print() const
          {
              printf("%s at %p (%d bytes)\n", kind_string[kind], address, size);
          }
  
          bool must_keep_searching_for(void* address)
          {
              return kind == TOMBSTONE || (in_use() &amp;&amp; address != this-&gt;address);
          }
  
          bool canaries_alive() const
          {
              bool alive = true;
              if (canary_dead(address - sizeof CANARY))
              {
                  printf("ERROR:    buffer underflow at %p\n", address);
                  alive = false;
              }
              if (canary_dead(address + size))
              {
                  printf("ERROR:     buffer overflow at %p\n", address);
                  alive = false;
              }
              return alive;
          }
      };
  
      const size_t MINIMUM_CAPACITY = 11;
  
      class hashtable
      {
          metadata* data;
          size_t used;
          size_t capacity;
          size_t tombstones;
  
      public:
  
          size_t size() const
          {
              return used - tombstones;
          }
  
          void print() const
          {
              for (size_t i = 0; i &lt; capacity; ++i)
              {
                  if (data[i].in_use())
                  {
                      printf(":( leaked ");
                      data[i].print();
                  }
              }
          }
  
          hashtable()
          {
              used = 0;
              capacity = MINIMUM_CAPACITY;
              data = static_cast&lt;metadata*&gt;(calloc(capacity, sizeof(metadata)));
              tombstones = 0;
          }
  
          ~hashtable()
          {
              free(data);
          }
  
          hashtable(const hashtable&amp; that)
          {
              used = 0;
              capacity = 3 * that.size() | 1;
              if (capacity &lt; MINIMUM_CAPACITY) capacity = MINIMUM_CAPACITY;
              data = static_cast&lt;metadata*&gt;(calloc(capacity, sizeof(metadata)));
              tombstones = 0;
  
              for (size_t i = 0; i &lt; that.capacity; ++i)
              {
                  if (that.data[i].in_use())
                  {
                      insert_unsafe(that.data[i]);
                  }
              }
          }
  
          hashtable&amp; operator=(hashtable copy)
          {
              swap(copy);
              return *this;
          }
  
          void swap(hashtable&amp; that)
          {
              my_swap(data, that.data);
              my_swap(used, that.used);
              my_swap(capacity, that.capacity);
              my_swap(tombstones, that.tombstones);
          }
  
          void insert_unsafe(const metadata&amp; x)
          {
              *find(x.address) = x;
              ++used;
          }
  
          void insert(const metadata&amp; x)
          {
              if (2 * used &gt;= capacity)
              {
                  hashtable copy(*this);
                  swap(copy);
              }
              insert_unsafe(x);
          }
  
          metadata* find(void* address)
          {
              size_t index = reinterpret_cast&lt;size_t&gt;(address) % capacity;
              while (data[index].must_keep_searching_for(address))
              {
                  ++index;
                  if (index == capacity) index = 0;
              }
              return &amp;data[index];
          }
  
          void erase(metadata* it)
          {
              it-&gt;kind = TOMBSTONE;
              ++tombstones;
          }
      } the_hashset;
  
      struct heap_debugger
      {
          heap_debugger()
          {
              puts("heap debugger started");
          }
  
          ~heap_debugger()
          {
              the_hashset.print();
              puts("heap debugger shutting down");
          }
      } the_heap_debugger;
  
      void* allocate(size_t size, kind_of_memory kind) throw (std::bad_alloc)
      {
          byte* raw = static_cast&lt;byte*&gt;(malloc(size + 2 * sizeof CANARY));
          if (raw == 0) throw std::bad_alloc();
  
          memcpy(raw, CANARY, sizeof CANARY);
          byte* payload = raw + sizeof CANARY;
          memcpy(payload + size, CANARY, sizeof CANARY);
  
          metadata md = {payload, size, kind};
          the_hashset.insert(md);
          printf("allocated ");
          md.print();
          return payload;
      }
  
      void release(void* payload, kind_of_memory kind) throw ()
      {
          if (payload == 0) return;
  
          metadata* p = the_hashset.find(payload);
  
          if (!p-&gt;in_use())
          {
              printf("ERROR:   no dynamic memory at %p\n", payload);
          }
          else if (p-&gt;kind != kind)
          {
              printf("ERROR:wrong form of delete at %p\n", payload);
          }
          else if (p-&gt;canaries_alive())
          {
              printf("releasing ");
              p-&gt;print();
              free(static_cast&lt;byte*&gt;(payload) - sizeof CANARY);
              the_hashset.erase(p);
          }
      }
  }
  
  void* operator new(size_t size) throw (std::bad_alloc)
  {
      return allocate(size, NON_ARRAY_MEMORY);
  }
  
  void* operator new[](size_t size) throw (std::bad_alloc)
  {
      return allocate(size, ARRAY_MEMORY);
  }
  
  void operator delete(void* payload) throw ()
  {
      release(payload, NON_ARRAY_MEMORY);
  }
  
  void operator delete[](void* payload) throw ()
  {
      release(payload, ARRAY_MEMORY);
  }
  
  int main()
  {
      int* p = new int[1];
      delete p;   // wrong form of delete
      delete[] p; // ok
      delete p;   // no dynamic memory (double delete)
  
      p = new int[1];
      p[-1] = 0xcafebabe;
      p[+1] = 0x12345678;
      delete[] p; // underflow and overflow prevent release
                  // p is not released, hence leak
  }
  </code></pre>