Issue 7913 - LMDB: bugs in mdb_cursor_get(*_DUP)
Summary: LMDB: bugs in mdb_cursor_get(*_DUP)
Status: VERIFIED FIXED
Alias: None
Product: LMDB
Classification: Unclassified
Component: liblmdb (show other issues)
Version: unspecified
Hardware: All All
: --- normal
Target Milestone: ---
Assignee: OpenLDAP project
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2014-07-30 19:14 UTC by batterseapower@hotmail.com
Modified: 2020-03-12 15:54 UTC (History)
0 users

See Also:


Attachments

Note You need to log in before you can comment on or make changes to this issue.
Description batterseapower@hotmail.com 2014-07-30 19:14:33 UTC
Full_Name: Max Bolingbroke
Version: LMDB HEAD
OS: OS X
URL: ftp://ftp.openldap.org/incoming/max-bolingbroke-140730.patch
Submission from: (NULL) (81.111.197.81)


1. When using mdb_cursor_get(MDB_FIRST_DUP) or mdb_cursor_get(MDB_LAST_DUP) on a
cursor that is currently positioned on a key without any duplicate values, then
we should return MDB_NOTFOUND rather than EINVAL.
2. When using mdb_cursor_get(MDB_NEXT_DUP) on a cursor that is currently
positioned on the final key in the database, we should not return MDB_NOTFOUND
unless the value we are on is actually the final one within that key.

In particular I claim that the following C program should run to completion
without any errors. It does not, but the attached patch
(max-bolingbroke-140730.patch) makes it do so.

I, Maximilian Bolingbroke, hereby place the attached modifications to liblmdb
(and only these modifications) into the public domain. Hence, these
modifications may be freely used and/or redistributed for any purpose with or
without attribution and/or other notice.

#define _XOPEN_SOURCE 500
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdarg.h>
#include "lmdb.h"

void panic(const char * restrict format, ...) {
	va_list argp;
	va_start(argp, format);
	vprintf(format, argp);
	va_end(argp);

	exit(1);
}

void mdb_check(char *context, int rc) {
	if (rc != 0) {
		panic("%s: %s", context, mdb_strerror(rc));
	}
}

void mdb_check_notfound(char *context, int rc) {
	if (rc != MDB_NOTFOUND) {
		panic("%s: %s", context, mdb_strerror(rc));
	}
}

int main(int argc, char **argv) {
	srand(1337);

	MDB_env *env;
	mdb_check("mdb_env_create", mdb_env_create(&env));
	mdb_check("mdb_env_set_maxdbs", mdb_env_set_maxdbs(env, 1));
	mdb_check("mdb_env_set_mapsize", mdb_env_set_mapsize(env, 1024 * 1024));
	mdb_check("mdb_env_open", mdb_env_open(env, "testdb", MDB_NOSUBDIR, 0644));

	MDB_txn *txn;
	mdb_check("mdb_txn_begin", mdb_txn_begin(env, NULL, 0, &txn));

	MDB_dbi dbi;
	mdb_check("mdb_dbi_open", mdb_dbi_open(txn, "root", MDB_CREATE | MDB_DUPSORT,
&dbi));

	int key;
	int value;

	MDB_val keyBuffer;
	keyBuffer.mv_size = sizeof(int);
	keyBuffer.mv_data = &key;

	MDB_val valueBuffer;
	valueBuffer.mv_size = sizeof(int);
	valueBuffer.mv_data = &value;

	{
		key = 1; value = 100;
		mdb_check("mdb_put", mdb_put(txn, dbi, &keyBuffer, &valueBuffer, 0));

		key = 2; value = 200; 
		mdb_check("mdb_put", mdb_put(txn, dbi, &keyBuffer, &valueBuffer, 0));

		key = 2; value = 201;
		mdb_check("mdb_put", mdb_put(txn, dbi, &keyBuffer, &valueBuffer, 0));

		//AAA:key = 3; value = 300;
		//AAA:mdb_check("mdb_put", mdb_put(txn, dbi, &keyBuffer, &valueBuffer, 0));
	}

	{
		MDB_cursor *cursor;
		mdb_check("mdb_cursor_open", mdb_cursor_open(txn, dbi, &cursor));

		// BUG 1
		// =====
		// The MDB_FIRST_DUP/MDB_LAST_DUP moves fail (they should leave the cursor
unchanged and return 0)
		// This seems to happen because the key "1" only has a single item and
mdb.c:5836 does not handle that properly.
		mdb_check("mdb_cursor_get", mdb_cursor_get(cursor, &keyBuffer, &valueBuffer,
MDB_FIRST));
		mdb_check_notfound("mdb_cursor_get(MDB_NEXT_DUP)",  mdb_cursor_get(cursor,
&keyBuffer, &valueBuffer, MDB_NEXT_DUP));
		mdb_check_notfound("mdb_cursor_get(MDB_PREV_DUP)",  mdb_cursor_get(cursor,
&keyBuffer, &valueBuffer, MDB_PREV_DUP));
		mdb_check_notfound("mdb_cursor_get(MDB_FIRST_DUP)", mdb_cursor_get(cursor,
&keyBuffer, &valueBuffer, MDB_FIRST_DUP));
		mdb_check_notfound("mdb_cursor_get(MDB_LAST_DUP)",  mdb_cursor_get(cursor,
&keyBuffer, &valueBuffer, MDB_LAST_DUP));

		// BUG 2
		// =====
		// This fails in a slightly different way because the key "2" has multiple
items. Specifically, the MDB_NEXT_DUP call
		// fails. If you uncomment all lines beginning with "//AAA:" to add the key
"3" to the database
		// (i.e. add it just after the key we are cursoring around in here), then it
works as I expect. I think
		// the problem is that the test for EOF at mdb.c:5267 is bailing us out, when
it should
		// instead be checking whether the subcursor has any items.
		mdb_check("mdb_cursor_get", mdb_cursor_get(cursor, &keyBuffer, &valueBuffer,
MDB_LAST));
		//AAA:mdb_check("mdb_cursor_get", mdb_cursor_get(cursor, &keyBuffer,
&valueBuffer, MDB_PREV));
		mdb_check("mdb_cursor_get(MDB_PREV_DUP)",  mdb_cursor_get(cursor, &keyBuffer,
&valueBuffer, MDB_PREV_DUP));
		mdb_check("mdb_cursor_get(MDB_NEXT_DUP)",  mdb_cursor_get(cursor, &keyBuffer,
&valueBuffer, MDB_NEXT_DUP));
		mdb_check("mdb_cursor_get(MDB_FIRST_DUP)", mdb_cursor_get(cursor, &keyBuffer,
&valueBuffer, MDB_FIRST_DUP));
		mdb_check("mdb_cursor_get(MDB_LAST_DUP)",  mdb_cursor_get(cursor, &keyBuffer,
&valueBuffer, MDB_LAST_DUP));

		mdb_cursor_close(cursor);
	}
	
	mdb_check("mdb_txn_commit", mdb_txn_commit(txn));

	return 0;
}
Comment 1 Howard Chu 2014-07-31 10:30:06 UTC
changed notes
changed state Open to Test
moved from Incoming to Software Bugs
Comment 2 Howard Chu 2014-07-31 16:34:08 UTC
batterseapower@hotmail.com wrote:
> Full_Name: Max Bolingbroke
> Version: LMDB HEAD
> OS: OS X
> URL: ftp://ftp.openldap.org/incoming/max-bolingbroke-140730.patch
> Submission from: (NULL) (81.111.197.81)
>
>
> 1. When using mdb_cursor_get(MDB_FIRST_DUP) or mdb_cursor_get(MDB_LAST_DUP) on a
> cursor that is currently positioned on a key without any duplicate values, then
> we should return MDB_NOTFOUND rather than EINVAL.

Rethinking this, I think it should simply return the existing non-dup value. 
mdb_cursor_count already handles a similar situation, returning 1 for the 
count when there are no dups.

> 2. When using mdb_cursor_get(MDB_NEXT_DUP) on a cursor that is currently
> positioned on the final key in the database, we should not return MDB_NOTFOUND
> unless the value we are on is actually the final one within that key.

OK.

-- 
   -- Howard Chu
   CTO, Symas Corp.           http://www.symas.com
   Director, Highland Sun     http://highlandsun.com/hyc/
   Chief Architect, OpenLDAP  http://www.openldap.org/project/

Comment 3 Howard Chu 2014-07-31 17:01:45 UTC
hyc@symas.com wrote:
> batterseapower@hotmail.com wrote:
>> Full_Name: Max Bolingbroke
>> Version: LMDB HEAD
>> OS: OS X
>> URL: ftp://ftp.openldap.org/incoming/max-bolingbroke-140730.patch
>> Submission from: (NULL) (81.111.197.81)
>>
>>
>> 1. When using mdb_cursor_get(MDB_FIRST_DUP) or mdb_cursor_get(MDB_LAST_DUP) on a
>> cursor that is currently positioned on a key without any duplicate values, then
>> we should return MDB_NOTFOUND rather than EINVAL.
>
> Rethinking this, I think it should simply return the existing non-dup value.
> mdb_cursor_count already handles a similar situation, returning 1 for the
> count when there are no dups.
>
>> 2. When using mdb_cursor_get(MDB_NEXT_DUP) on a cursor that is currently
>> positioned on the final key in the database, we should not return MDB_NOTFOUND
>> unless the value we are on is actually the final one within that key.
>
> OK.
>
Alternate fixes in mdb.master.

-- 
   -- Howard Chu
   CTO, Symas Corp.           http://www.symas.com
   Director, Highland Sun     http://highlandsun.com/hyc/
   Chief Architect, OpenLDAP  http://www.openldap.org/project/

Comment 4 OpenLDAP project 2014-08-01 21:04:52 UTC
fixed in mdb.master
Comment 5 Quanah Gibson-Mount 2014-12-11 01:03:00 UTC
changed state Test to Closed