(ITS#7754) Unaligned MDB_DUPSORT sub-pages

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

Full_Name: Hallvard B Furuseth
Version: LMDB_0.9.10
OS: Linux x86_64
URL: 
Submission from: (NULL) (81.191.45.35)
Submitted by: hallvard


Uneven-sized keys in MDB_DUPSORT databases get unaligned sub-pages,
and thus everything inside their sub-pages gets unaligned too.

A fix preserving the current format when !MISALIGNED_OK would be more
memcpying, e.g. in COPY_PGNO(). dcmp functions would do byte by byte
comparison for such sub-pages.  MDB_page.mp_flags could be split
two uint8_t fields: mp_flags, mp_zero (zero for now anyway).
Renumber P_KEEP to 0x80 or P_META.


A fix with a format change would be to put the padding byte in front
of the sub-page instead of at the end.

One fix with a format change could be that the data item gets uneven
size too, with a padding byte in front of the sub-page.

The most general way would be to do that in all nodes with uneven-
sized key and even-sized data:

#define NODEDATA(node) ((void *) ((char *)(node)->mn_data + \
    (node)->mn_ksize + ((node)->mn_ksize & ~(node)->mn_lo & 1)))

Or do it only with sub-pages.  Make the data item uneven-sized so
code which is not interested in whether this is a sub-page, need
not know about the hack.  Access the sub-page specially:

#define NODEPAGE(node) ((MDB_page *) \
    ((char *)(node)->mn_data + (((node)->mn_ksize + 1) & -2)))

That could be coded so the old format is still readable.  Then a
utility can walk all databases and adjust sub-pages so they have
padding in front instead of at the end, so no dump/reload will be
needed:

/** Address of the possibly 2-byte aligned sub-page in a node.
 *  If the data item has uneven size, then the first byte is
 *  padding to re-align the sub-page after an uneven-sized key.
 */
#define NODEPAGE(node) ((MDB_page *) \
    ((char *)(node)->mn_data + (node)->mn_ksize + ((node)->mn_lo & 1)))