[slides/code/10-heaps-huffman] container-overflow in binary_heap::percolateDown(int)

[smasher164]

Caught with AddressSanitizer (clang++ main.cpp binary_heap.cpp -g -fsanitize=address):
Here's main.cpp:

#include "binary_heap.h"

int main() {
  binary_heap heap;
  heap.insert(2);
  heap.insert(1);
  while (heap.size() > 1) {
    int a = heap.deleteMin();
    int b = heap.deleteMin();
    int parent = a + b;
    heap.insert(parent);
  }
}

./a.out outputs:

=================================================================
==42974==ERROR: AddressSanitizer: container-overflow on address 0x6030000002b4 at pc 0x0001024e6aac bp 0x7fff5d71bd60 sp 0x7fff5d71bd58
READ of size 4 at 0x6030000002b4 thread T0
    #0 0x1024e6aab in binary_heap::percolateDown(int) binary_heap.cpp:63
    #1 0x1024e86ff in binary_heap::deleteMin() binary_heap.cpp:56
    #2 0x1024e4549 in main main.cpp:13
    #3 0x7fffab008234 in start (libdyld.dylib:x86_64+0x5234)

0x6030000002b4 is located 4 bytes inside of 32-byte region [0x6030000002b0,0x6030000002d0)
allocated by thread T0 here:
    #0 0x10256414b in wrap__Znwm (libclang_rt.asan_osx_dynamic.dylib:x86_64h+0x6414b)
    #1 0x1024ec85c in std::__1::__split_buffer<int, std::__1::allocator<int>&>::__split_buffer(unsigned long, unsigned long, std::__1::allocator<int>&) __split_buffer:311
    #2 0x1024ea98c in std::__1::__split_buffer<int, std::__1::allocator<int>&>::__split_buffer(unsigned long, unsigned long, std::__1::allocator<int>&) __split_buffer:310
    #3 0x1024e9b61 in void std::__1::vector<int, std::__1::allocator<int> >::__push_back_slow_path<int const>(int const&) vector:1570
    #4 0x1024e768b in binary_heap::insert(int) binary_heap.cpp:29
    #5 0x1024e4502 in main main.cpp:10
    #6 0x7fffab008234 in start (libdyld.dylib:x86_64+0x5234)

HINT: if you don't care about these errors you may set ASAN_OPTIONS=detect_container_overflow=0.
If you suspect a false positive see also: https://github.com/google/sanitizers/wiki/AddressSanitizerContainerOverflow.
SUMMARY: AddressSanitizer: container-overflow binary_heap.cpp:63 in binary_heap::percolateDown(int)
Shadow bytes around the buggy address:
  0x1c0600000000: fa fa 00 00 00 fa fa fa 00 00 00 00 fa fa 00 00
  0x1c0600000010: 00 00 fa fa 00 00 00 00 fa fa fd fd fd fa fa fa
  0x1c0600000020: fd fd fd fd fa fa 00 00 00 00 fa fa 00 00 00 fa
  0x1c0600000030: fa fa 00 00 00 fa fa fa 00 00 00 00 fa fa fd fd
  0x1c0600000040: fd fa fa fa fd fd fd fd fa fa 00 00 00 fa fa fa
=>0x1c0600000050: 00 00 00 00 fa fa[04]fc fc fc fa fa fa fa fa fa
  0x1c0600000060: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c0600000070: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c0600000080: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c0600000090: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x1c06000000a0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==42974==ABORTING

The error comes from deleteMin where percolateDown is called after heap.pop_back() and hole == size() for a heap that has a single node. The reason why this doesn't usually error out on most runs is because the vector doesn't zero the element at that position unless it has to resize.

Changing percolateDown to use heap.at demonstrates this fact:

libc++abi.dylib: terminating with uncaught exception of type std::out_of_range: vector
Abort trap: 6

Students might notice the error if their heap elements are pointers to dynamically allocated objects. The solution is to therefore percolateDown(1) before pop_back() inside of deleteMin.