SQLite

#
# This script looks for memory leaks by analyzing the output of "sqlite" 
# when compiled with the SQLITE_DEBUG=2 option.
#
/[0-9]+ malloc / {
  mem[$6] = $0
}
/[0-9]+ realloc / {
  mem[$8] = "";
  mem[$10] = $0
}
/[0-9]+ free / {
  if (mem[$6]=="") {
    print "*** free without a malloc at",$6
  }
  mem[$6] = "";
  str[$6] = ""
}
/^string at / {
  addr = $4
  sub("string at " addr " is ","")
  str[addr] = $0
}
END {
  for(addr in mem){
    if( mem[addr]=="" ) continue
    print mem[addr], str[addr]
  }
}

# This AWK script reads the output of testfixture when compiled for memory
# debugging.  It generates SQL commands that can be fed into an sqlite 
# instance to determine what memory is never freed.  A typical usage would
# be as follows:
#
#     make -f memleak.mk fulltest 2>mem.out
#     awk -f ../sqlite/tool/memleak2.awk mem.out | ./sqlite :memory:
#
# The job performed by this script is the same as that done by memleak.awk.
# The difference is that this script uses much less memory when the size
# of the mem.out file is huge.
#
BEGIN {
  print "CREATE TABLE mem(loc INTEGER PRIMARY KEY, src);"
}
/[0-9]+ malloc / {
  print "INSERT INTO mem VALUES(" strtonum($6) ",'" $0 "');"
}
/[0-9]+ realloc / {
  print "INSERT INTO mem VALUES(" strtonum($10) \
           ",(SELECT src FROM mem WHERE loc=" strtonum($8) "));"
  print "DELETE FROM mem WHERE loc=" strtonum($8) ";"
}
/[0-9]+ free / {
  print "DELETE FROM mem WHERE loc=" strtonum($6) ";"
}
END {
  print "SELECT src FROM mem;"
}

#/bin/sh
# \
exec `which tclsh` $0 "$@"
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
######################################################################

set doco "
This script is a tool to help track down memory leaks in the sqlite
library. The library must be compiled with the preprocessor symbol
SQLITE_MEMDEBUG set to at least 2. It must be set to 3 to enable stack 
traces.

To use, run the leaky application and save the standard error output.
Then, execute this program with the first argument the name of the
application binary (or interpreter) and the second argument the name of the
text file that contains the collected stderr output.

If all goes well a summary of unfreed allocations is printed out. If the
GNU C library is in use and SQLITE_DEBUG is 3 or greater a stack trace is
printed out for each unmatched allocation.

If the \"-r <n>\" option is passed, then the program stops and prints out
the state of the heap immediately after the <n>th call to malloc() or
realloc().

Example:

$ ./testfixture ../sqlite/test/select1.test 2> memtrace.out
$ tclsh $argv0 ?-r <malloc-number>? ./testfixture memtrace.out
"


proc usage {} {
  set prg [file tail $::argv0]
  puts "Usage: $prg ?-r <malloc-number>? <binary file> <mem trace file>"
  puts ""
  puts [string trim $::doco]
  exit -1
}

proc shift {listvar} {
  upvar $listvar l
  set ret [lindex $l 0]
  set l [lrange $l 1 end]
  return $ret
}

# Argument handling. The following vars are set:
#
# $exe       - the name of the executable (i.e. "testfixture" or "./sqlite3")
# $memfile   - the name of the file containing the trace output.
# $report_at - The malloc number to stop and report at. Or -1 to read 
#              all of $memfile.
#
set report_at -1
while {[llength $argv]>2} {
  set arg [shift argv]
  switch -- $arg {
    "-r" {
      set report_at [shift argv]
    }
    default {
      usage
    }
  }
}
if {[llength $argv]!=2} usage
set exe [lindex $argv 0]
set memfile [lindex $argv 1]

# If stack traces are enabled, the 'addr2line' program is called to
# translate a binary stack address into a human-readable form.
set addr2line addr2line

# When the SQLITE_MEMDEBUG is set as described above, SQLite prints
# out a line for each malloc(), realloc() or free() call that the
# library makes. If SQLITE_MEMDEBUG is 3, then a stack trace is printed
# out before each malloc() and realloc() line.
#
# This program parses each line the SQLite library outputs and updates
# the following global Tcl variables to reflect the "current" state of
# the heap used by SQLite.
#
set nBytes 0               ;# Total number of bytes currently allocated.
set nMalloc 0              ;# Total number of malloc()/realloc() calls.
set nPeak 0                ;# Peak of nBytes.
set iPeak 0                ;# nMalloc when nPeak was set.
#
# More detailed state information is stored in the $memmap array. 
# Each key in the memmap array is the address of a chunk of memory
# currently allocated from the heap. The value is a list of the 
# following form
# 
#     {<number-of-bytes> <malloc id> <stack trace>}
#
array unset memmap

proc process_input {input_file array_name} {
  upvar $array_name mem 
  set input [open $input_file]

  set MALLOC {([[:digit:]]+) malloc ([[:digit:]]+) bytes at 0x([[:xdigit:]]+)}
  # set STACK {^[[:digit:]]+: STACK: (.*)$}
  set STACK {^STACK: (.*)$}
  set FREE {[[:digit:]]+ free ([[:digit:]]+) bytes at 0x([[:xdigit:]]+)}
  set REALLOC {([[:digit:]]+) realloc ([[:digit:]]+) to ([[:digit:]]+)}
  append REALLOC { bytes at 0x([[:xdigit:]]+) to 0x([[:xdigit:]]+)}

  set stack ""
  while { ![eof $input] } {
    set line [gets $input]
    if {[regexp $STACK $line dummy stack]} {
      # Do nothing. The variable $stack now stores the hexadecimal stack dump
      # for the next malloc() or realloc().

    } elseif { [regexp $MALLOC $line dummy mallocid bytes addr]  } {
      # If this is a 'malloc' line, set an entry in the mem array. Each entry
      # is a list of length three, the number of bytes allocated , the malloc
      # number and the stack dump when it was allocated.
      set mem($addr) [list $bytes "malloc $mallocid" $stack]
      set stack ""

      # Increase the current heap usage
      incr ::nBytes $bytes

      # Increase the number of malloc() calls
      incr ::nMalloc

      if {$::nBytes > $::nPeak} {
        set ::nPeak $::nBytes
        set ::iPeak $::nMalloc
      }

    } elseif { [regexp $FREE $line dummy bytes addr] } {
      # If this is a 'free' line, remove the entry from the mem array. If the 
      # entry does not exist, or is the wrong number of bytes, announce a
      # problem. This is more likely a bug in the regular expressions for
      # this script than an SQLite defect.
      if { [lindex $mem($addr) 0] != $bytes } {
        error "byte count mismatch"
      }
      unset mem($addr) 

      # Decrease the current heap usage
      incr ::nBytes [expr -1 * $bytes]

    } elseif { [regexp $REALLOC $line dummy mallocid ob b oa a] } {
      # "free" the old allocation in the internal model:
      incr ::nBytes [expr -1 * $ob]
      unset mem($oa);

      # "malloc" the new allocation
      set mem($a) [list $b "realloc $mallocid" $stack]
      incr ::nBytes $b
      set stack ""

      # Increase the number of malloc() calls
      incr ::nMalloc

      if {$::nBytes > $::nPeak} {
        set ::nPeak $::nBytes
        set ::iPeak $::nMalloc
      }

    } else {
      # puts "REJECT: $line"
    }

    if {$::nMalloc==$::report_at} report
  }

  close $input
}

proc printstack {stack} {
  set fcount 10
  if {[llength $stack]<10} {
    set fcount [llength $stack]
  }
  foreach frame [lrange $stack 1 $fcount] {
    foreach {f l} [split [exec $::addr2line -f --exe=$::exe $frame] \n] {}
    puts [format "%-30s %s" $f $l]
  }
  if {[llength $stack]>0 } {puts ""}
}

proc report {} {

  foreach key [array names ::memmap] {
    set stack [lindex $::memmap($key) 2]
    set bytes [lindex $::memmap($key) 0]
    lappend summarymap($stack) $bytes
  }

  set sorted [list]
  foreach stack [array names summarymap] {
    set allocs $summarymap($stack)
    set sum 0
    foreach a $allocs {
      incr sum $a
    }
    lappend sorted [list $sum $stack]
  }

  set sorted [lsort -integer -index 0 $sorted]
  foreach s $sorted {
    set sum [lindex $s 0]
    set stack [lindex $s 1]
    set allocs $summarymap($stack)
    puts "$sum bytes in [llength $allocs] chunks ($allocs)"
    printstack $stack
  }

  # Print out summary statistics
  puts "Total allocations            : $::nMalloc"
  puts "Total outstanding allocations: [array size ::memmap]" 
  puts "Current heap usage           : $::nBytes bytes"
  puts "Peak heap usage              : $::nPeak bytes (malloc #$::iPeak)"

  exit
}

process_input $memfile memmap
report

The SQL database used for ACD contains 113 tables and indices implemented
in GDBM.  The following are statistics on the sizes of keys and data
within these tables and indices.

Entries:      962080
Size:         45573853
Avg Size:     48
Key Size:     11045299
Avg Key Size: 12
Max Key Size: 99


 Size of key              Cummulative
  and data     Instances  Percentage
------------  ----------  -----------
    0..8            266    0%
    9..12          5485    0%
   13..16         73633    8%
   17..24        180918   27%
   25..32        209823   48%
   33..40        148995   64%
   41..48         76304   72%
   49..56         14346   73%
   57..64         15725   75%
   65..80         44916   80%
   81..96        127815   93%
   97..112        34769   96%
  113..128        13314   98%
  129..144         8098   99%
  145..160         3355   99%
  161..176         1159   99%
  177..192          629   99%
  193..208          221   99%
  209..224          210   99%
  225..240          129   99%
  241..256           57   99%
  257..288          496   99%
  289..320           60   99%
  321..352           37   99%
  353..384           46   99%
  385..416           22   99%
  417..448           24   99%
  449..480           26   99%
  481..512           27   99%
  513..1024         471   99%
 1025..2048         389   99%
 2049..4096         182   99%
 4097..8192          74   99%
 8193..16384         34   99%
16385..32768         17   99%
32769..65536          5   99%
65537..131073         3  100%


This information is gathered to help design the new built-in
backend for sqlite 2.0.  Note in particular that 99% of all
database entries have a combined key and data size of less than
144 bytes.  So if a leaf node in the new database is able to
store 144 bytes of combined key and data, only 1% of the leaves
will require overflow pages.  Furthermore, note that no key
is larger than 99 bytes, so if the key will never be on an
overflow page.

The average combined size of key+data is 48.  Add in 16 bytes of
overhead for a total of 64.  That means that a 1K page will
store (on average) about 16 entries.