OpenLDAP
Up to top level
Build   Contrib   Development   Documentation   Historical   Incoming   Software Bugs   Software Enhancements   Web  

Logged in as guest

Viewing Software Bugs/7970
Full headers

From: leo@yuriev.ru
Subject: LMDB: Critical Heisenbug - Inconsistent reading & SIGSEGV due to the race condition.
Compose comment
Download message
State:
0 replies:
3 followups: 1 2 3

Major security issue: yes  no

Notes:

Notification:


Date: Fri, 17 Oct 2014 22:26:22 +0000
From: leo@yuriev.ru
To: openldap-its@OpenLDAP.org
Subject: LMDB: Critical Heisenbug - Inconsistent reading & SIGSEGV due to the race condition.
Full_Name: Leonid Yuriev
Version: 2.4.40
OS: RHEL7
URL: ftp://ftp.openldap.org/incoming/
Submission from: (NULL) (31.130.36.33)


In continue of ITS#7969.

Because of a race condition between readers and writer's activity for FreeDB
reclaiming in case it is nearly empty, some pages that used by reader, may be 
reused for a new txn. Thereby reader may get an unpredictable rubbish, throw an
assertion failure or SIGSEGV.

I am sure, the race condition is present, exactly between reader's mr_txnid and
last transaction mti_txnid, which is updated by the writer.

Let see to line 2525 of mdb_txn_renew0() in stable 2.4.40
http://www.openldap.org/devel/gitweb.cgi?p=openldap.git;a=blob;f=libraries/liblmdb/mdb.c;h=6cc343326efeb8543db073671e92625723daf938;hb=e648bdc22cd654d371a224a88973f986f67ba499#l2525

The code is:
txn->mt_txnid = r-EmEmr_txnid = ti->mti_txnid;

From a CPU's point of view it is:
step #1, reg = ti->mti_txnid /* load the last txn-id from environment to
register */
step #2, r->mr_txnid = reg /* write txn-id into the reader table */
step #3, txn->mt_txnid = reg

The r->mr_txnid is used by mdb_find_oldest() for lookup a txn-id that is
available for reclaim from FreeDB by mdb_page_alloc().


When the reader's thread doing these steps, the writer can commit a several
transactions and the ti->mti_txnid may be changed between steps 1 and 2.
Before
the step 2, a writer is free to reclaim any records from FreeDB (except the
last).
Thereby, the writer can commit several new transactions and reclaim several
records from FreeDB, include the txn which the reader has begun using at the
step1.
In this case the reader may be read a pages that is not contain the such txn any
longer, but the reclaimed pages, which may contain the _anything_ from a new
transaction.

It is hard to reproduce the problem, but we can change the code without altering
its significance, for instance: 
diff --git a/libraries/liblmdb/mdb.c b/libraries/liblmdb/mdb.c
index 6cc3433..c501a2e 100644
--- a/libraries/liblmdb/mdb.c
+++ b/libraries/liblmdb/mdb.c
@@ -2018,6 +2018,8 @@ mdb_page_alloc(MDB_cursor *mc, int num, MDB_page **mp)
 		if (oldest <= last) {
 			if (!found_old) {
 				oldest = mdb_find_oldest(txn);
+				/* LY: catch heisenbug. */
+				mdb_tassert(txn, oldest >= env->me_pgoldest);
 				env->me_pgoldest = oldest;
 				found_old = 1;
 			}
@@ -2034,6 +2036,8 @@ mdb_page_alloc(MDB_cursor *mc, int num, MDB_page **mp)
 		if (oldest <= last) {
 			if (!found_old) {
 				oldest = mdb_find_oldest(txn);
+				/* LY: catch heisenbug. */
+				mdb_tassert(txn, oldest >= env->me_pgoldest);
 		

Followup 1

Download message
Date: Sat, 18 Oct 2014 02:35:33 +0400
Subject: Re: (ITS#7970) LMDB: Critical Heisenbug - Inconsistent reading &
 SIGSEGV due to the race condition.
From: =?UTF-8?B?0JvQtdC+0L3QuNC0INCu0YDRjNC10LI=?= <leo@yuriev.ru>
To: openldap-its@openldap.org
The fix is really simple. The patch is attached below, but previously
volatile-fix of ITS is required.
Also, the simple testcase (make test), with an extra yields and the
couple of paranoid asserts, is:
diff --git a/libraries/liblmdb/mdb.c b/libraries/liblmdb/mdb.c
index 3286ffb..2558d6f 100644
--- a/libraries/liblmdb/mdb.c
+++ b/libraries/liblmdb/mdb.c
@@ -2018,6 +2018,8 @@ mdb_page_alloc(MDB_cursor *mc, int num, MDB_page **mp)
  if (oldest <= last) {
  if (!found_old) {
  oldest = mdb_find_oldest(txn);
+ /* LY: catch heisenbug. */
+ mdb_tassert(txn, oldest >= env->me_pgoldest);
  env->me_pgoldest = oldest;
  found_old = 1;
  }
@@ -2034,6 +2036,8 @@ mdb_page_alloc(MDB_cursor *mc, int num, MDB_page **mp)
  if (oldest <= last) {
  if (!found_old) {
  oldest = mdb_find_oldest(txn);
+ /* LY: catch heisenbug. */
+ mdb_tassert(txn, oldest >= env->me_pgoldest);
  env->me_pgoldest = oldest;
  found_old = 1;
  }
@@ -2522,7 +2526,16 @@ mdb_txn_renew0(MDB_txn *txn)
  return rc;
  }
  }
- txn->mt_txnid = r->mr_txnid = ti->mti_txnid;
+ do {
+ r->mr_txnid = ti->mti_txnid;
+ sched_yield();
+ sched_yield();
+ sched_yield();
+ } while(r->mr_txnid != ti->mti_txnid);
+ sched_yield();
+ sched_yield();
+ sched_yield();
+ txn->mt_txnid = r->mr_txnid;
  txn->mt_u.reader = r;
  meta = env->me_metas[txn->mt_txnid & 1];
  }

---

The attached files is derived from OpenLDAP Software. All of the modifications
to OpenLDAP Software represented in the following patch(es) were developed by
Peter-Service LLC, Moscow, Russia. Peter-Service LLC has not assigned rights
and/or interest in this work to any party. I, Leonid Yuriev am authorized by
Peter-Service LLC, my employer, to release this work under the following terms.

Peter-Service LLC hereby places the following modifications to OpenLDAP Software
(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.

commit 6028662665c09f4d34b751bfd9b09223f6cb2433
Author: Leo Yuriev <leo@yuriev.ru>
Date:   2014-10-17 23:29:56 +0400

    ITS#7970 for LMDB: the Heisenbug.

diff --git a/libraries/liblmdb/mdb.c b/libraries/liblmdb/mdb.c
index 3286ffb..83a15c1 100644
--- a/libraries/liblmdb/mdb.c
+++ b/libraries/liblmdb/mdb.c
@@ -2522,7 +2522,12 @@ mdb_txn_renew0(MDB_txn *txn)
  return rc;
  }
  }
- txn->mt_txnid = r->mr_txnid = ti->mti_txnid;
+
+ do /* LY: Retry on a race, ITS#7970. */
+ r->mr_txnid = ti->mti_txnid;
+ while(r->mr_txnid != ti->mti_txnid);
+
+ txn->mt_txnid = r->mr_txnid;
  txn->mt_u.reader = r;
  meta = env->me_metas[txn->mt_txnid & 1];
  }



Followup 2

Download message
Date: Sat, 18 Oct 2014 02:55:06 +0400
Subject: Re: (ITS#7970) LMDB: Critical Heisenbug - Inconsistent reading &
 SIGSEGV due to the race condition.
From: =?UTF-8?B?0JvQtdC+0L3QuNC0INCu0YDRjNC10LI=?= <leo@yuriev.ru>
To: openldap-its@openldap.org
The attached files is derived from OpenLDAP Software. All of the modifications
to OpenLDAP Software represented in the following patch(es) were developed by
Peter-Service LLC, Moscow, Russia. Peter-Service LLC has not assigned rights
and/or interest in this work to any party. I, Leonid Yuriev am authorized by
Peter-Service LLC, my employer, to release this work under the following terms.

Peter-Service LLC hereby places the following modifications to OpenLDAP Software
(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.

https://gist.github.com/leo-yuriev/fc00313b8035cddba6a7



Followup 3

Download message
Date: Sat, 18 Oct 2014 07:14:27 +0100
From: Howard Chu <hyc@symas.com>
To: leo@yuriev.ru, openldap-its@OpenLDAP.org
Subject: Re: (ITS#7970) LMDB: Critical Heisenbug - Inconsistent reading &
 SIGSEGV due to the race condition.
Committed to mdb.master

> commit 6028662665c09f4d34b751bfd9b09223f6cb2433
> Author: Leo Yuriev <leo@yuriev.ru>
> Date:   2014-10-17 23:29:56 +0400
>
>      ITS#7970 for LMDB: the Heisenbug.
>
> diff --git a/libraries/liblmdb/mdb.c b/libraries/liblmdb/mdb.c
> index 3286ffb..83a15c1 100644
> --- a/libraries/liblmdb/mdb.c
> +++ b/libraries/liblmdb/mdb.c
> @@ -2522,7 +2522,12 @@ mdb_txn_renew0(MDB_txn *txn)
>    return rc;
>    }
>    }
> - txn->mt_txnid = r->mr_txnid = ti->mti_txnid;
> +
> + do /* LY: Retry on a race, ITS#7970. */
> + r->mr_txnid = ti->mti_txnid;
> + while(r->mr_txnid != ti->mti_txnid);
> +
> + txn->mt_txnid = r->mr_txnid;
>    txn->mt_u.reader = r;
>    meta = env->me_metas[txn->mt_txnid & 1];
>    }
>
>
>
>


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


Up to top level
Build   Contrib   Development   Documentation   Historical   Incoming   Software Bugs   Software Enhancements   Web  

Logged in as guest


The OpenLDAP Issue Tracking System uses a hacked version of JitterBug

______________
© Copyright 2013, OpenLDAP Foundation, info@OpenLDAP.org