(ITS#7772) liblmdb sub-page growth when adding existing data

[h.b.furuseth@usit.uio.no]

Full_Name: Hallvard B Furuseth
Version: mdb.master, 4c8f57615c5ca7b014c038e59c1045182e74f5ad
OS: Linux x86_64
URL: ftp://ftp.openldap.org/incoming/Hallvard-Furuseth-growth-131223.c
Submission from: (NULL) (81.191.45.35)
Submitted by: hallvard


A non-LEAF2 sub-page grows if you put() a data item which already
exists.  The space remains unused while the sub-page exists.
(A LEAF2 page grows reusable space, and only if it is full.)

Demo program enclosed.  Edit mdb.c to set mdb_debug=1 and build
with -DMDB_DEBUG.  Watch the 1st DPRINTF() in mdb_node_add():

bash$ ./a.out 2>&1 | perl -lne '/add to (.*) key size/ && print $1'
leaf page 2 index 0, data size 404    # node with 1st item
leaf page 2 index 0, data size 840    # convert to sub-page for 2nd item
leaf sub-page 2 index 0, data size 0
leaf sub-page 2 index 1, data size 0
leaf page 2 index 0, data size 1250   # space for re-adding 2nd item
leaf page 2 index 0, data size 1660   # space for re-adding 2nd item
leaf page 2 index 0, data size 48     # ...too big, moved to sub-DB.

Fix: lmdb could position cursor+xcursor fully before spill/touch,
with an MDB_GET_BOTH variant which returns different codes for "no
such key" and "no such data".  And position it before MDB_MULTIPLE
loops up.  The current comparisons to see if the data item exists,
go away.  Maybe mdb_cursor_put() gets split in several functions,
since much of the work in the recursive put()s will be unneeded.