/** @file mdb.c

* @brief Lightning memory-mapped database library

*

* A Btree-based database management library modeled loosely on the

* BerkeleyDB API, but much simplified.

*/

/*

* Copyright 2011-2021 Howard Chu, Symas Corp.

* All rights reserved.

*

* Redistribution and use in source and binary forms, with or without

* modification, are permitted only as authorized by the OpenLDAP

* Public License.

*

* A copy of this license is available in the file LICENSE in the

* top-level directory of the distribution or, alternatively, at

* <http://www.OpenLDAP.org/license.html>.

*

* This code is derived from btree.c written by Martin Hedenfalk.

*

* Copyright (c) 2009, 2010 Martin Hedenfalk <[email protected]>

*

* Permission to use, copy, modify, and distribute this software for any

* purpose with or without fee is hereby granted, provided that the above

* copyright notice and this permission notice appear in all copies.

*

* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES

* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF

* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR

* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES

* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN

* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF

* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

*/

#ifndef _GNU_SOURCE

#define _GNU_SOURCE 1

#endif

#if defined(MDB_VL32) || defined(__WIN64__)

#define _FILE_OFFSET_BITS 64

#endif

#ifdef _WIN32

#include <malloc.h>

#include <windows.h>

#include <wchar.h> /* get wcscpy() */

/* We use native NT APIs to setup the memory map, so that we can

* let the DB file grow incrementally instead of always preallocating

* the full size. These APIs are defined in <wdm.h> and <ntifs.h>

* but those headers are meant for driver-level development and

* conflict with the regular user-level headers, so we explicitly

* declare them here. We get pointers to these functions from

* NTDLL.DLL at runtime, to avoid buildtime dependencies on any

* NTDLL import libraries.

*/

typedef NTSTATUS (WINAPI NtCreateSectionFunc)

(OUT PHANDLE sh, IN ACCESS_MASK acc,

IN void * oa OPTIONAL,

IN PLARGE_INTEGER ms OPTIONAL,

IN ULONG pp, IN ULONG aa, IN HANDLE fh OPTIONAL);

static NtCreateSectionFunc *NtCreateSection;

typedef enum _SECTION_INHERIT {

ViewShare = 1,

ViewUnmap = 2

} SECTION_INHERIT;

typedef NTSTATUS (WINAPI NtMapViewOfSectionFunc)

(IN PHANDLE sh, IN HANDLE ph,

IN OUT PVOID *addr, IN ULONG_PTR zbits,

IN SIZE_T cs, IN OUT PLARGE_INTEGER off OPTIONAL,

IN OUT PSIZE_T vs, IN SECTION_INHERIT ih,

IN ULONG at, IN ULONG pp);

static NtMapViewOfSectionFunc *NtMapViewOfSection;

typedef NTSTATUS (WINAPI NtCloseFunc)(HANDLE h);

static NtCloseFunc *NtClose;

/** getpid() returns int; MinGW defines pid_t but MinGW64 typedefs it

* as int64 which is wrong. MSVC doesn't define it at all, so just

* don't use it.

*/

#define MDB_PID_T int

#define MDB_THR_T DWORD

#include <sys/types.h>

#include <sys/stat.h>

#ifdef __GNUC__

# include <sys/param.h>

#else

# define LITTLE_ENDIAN 1234

# define BIG_ENDIAN 4321

# define BYTE_ORDER LITTLE_ENDIAN

# ifndef SSIZE_MAX

# define SSIZE_MAX INT_MAX

# endif

#endif

#define MDB_OFF_T int64_t

#else

#include <sys/types.h>

#include <sys/stat.h>

#define MDB_PID_T pid_t

#define MDB_THR_T pthread_t

#include <sys/param.h>

#include <sys/uio.h>

#include <sys/mman.h>

#ifdef HAVE_SYS_FILE_H

#include <sys/file.h>

#endif

#include <fcntl.h>

#define MDB_OFF_T off_t

#endif

#if defined(__mips) && defined(__linux)

/* MIPS has cache coherency issues, requires explicit cache control */

#include <sys/cachectl.h>

#define CACHEFLUSH(addr, bytes, cache) cacheflush(addr, bytes, cache)

#else

#define CACHEFLUSH(addr, bytes, cache)

#endif

#if defined(__linux) && !defined(MDB_FDATASYNC_WORKS)

/** fdatasync is broken on ext3/ext4fs on older kernels, see

* description in #mdb_env_open2 comments. You can safely

* define MDB_FDATASYNC_WORKS if this code will only be run

* on kernels 3.6 and newer.

*/

#define BROKEN_FDATASYNC

#endif

#include <errno.h>

#include <limits.h>

#include <stddef.h>

#include <inttypes.h>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <time.h>

#ifdef _MSC_VER

#include <io.h>

typedef SSIZE_T ssize_t;

#else

#include <unistd.h>

#endif

#if defined(__sun) || defined(__ANDROID__)

/* Most platforms have posix_memalign, older may only have memalign */

#define HAVE_MEMALIGN 1

#include <malloc.h>

/* On Solaris, we need the POSIX sigwait function */

#if defined (__sun)

# define _POSIX_PTHREAD_SEMANTICS 1

#endif

#endif

#if !(defined(BYTE_ORDER) || defined(__BYTE_ORDER))

#include <netinet/in.h>

#include <resolv.h> /* defines BYTE_ORDER on HPUX and Solaris */

#endif

#if defined(__FreeBSD__) && defined(__FreeBSD_version) && __FreeBSD_version >= 1100110

# define MDB_USE_POSIX_MUTEX 1

# define MDB_USE_ROBUST 1

#elif defined(__APPLE__) || defined (BSD) || defined(__FreeBSD_kernel__)

# if !(defined(MDB_USE_POSIX_MUTEX) || defined(MDB_USE_POSIX_SEM))

# define MDB_USE_SYSV_SEM 1

# endif

# define MDB_FDATASYNC fsync

#elif defined(__ANDROID__)

# define MDB_FDATASYNC fsync

#endif

#ifndef _WIN32

#include <pthread.h>

#include <signal.h>

#ifdef MDB_USE_POSIX_SEM

# define MDB_USE_HASH 1

#include <semaphore.h>

#elif defined(MDB_USE_SYSV_SEM)

#include <sys/ipc.h>

#include <sys/sem.h>

#ifdef _SEM_SEMUN_UNDEFINED

union semun {

int val;

struct semid_ds *buf;

unsigned short *array;

};

#endif /* _SEM_SEMUN_UNDEFINED */

#else

#define MDB_USE_POSIX_MUTEX 1

#endif /* MDB_USE_POSIX_SEM */

#endif /* !_WIN32 */

#if defined(_WIN32) defined(MDB_USE_POSIX_SEM) defined(MDB_USE_SYSV_SEM) \

defined(MDB_USE_POSIX_MUTEX) != 1

# error "Ambiguous shared-lock implementation"

#endif

#ifdef USE_VALGRIND

#include <valgrind/memcheck.h>

#define VGMEMP_CREATE(h,r,z) VALGRIND_CREATE_MEMPOOL(h,r,z)

#define VGMEMP_ALLOC(h,a,s) VALGRIND_MEMPOOL_ALLOC(h,a,s)

#define VGMEMP_FREE(h,a) VALGRIND_MEMPOOL_FREE(h,a)

#define VGMEMP_DESTROY(h) VALGRIND_DESTROY_MEMPOOL(h)

#define VGMEMP_DEFINED(a,s) VALGRIND_MAKE_MEM_DEFINED(a,s)

#else

#define VGMEMP_CREATE(h,r,z)

#define VGMEMP_ALLOC(h,a,s)

#define VGMEMP_FREE(h,a)

#define VGMEMP_DESTROY(h)

#define VGMEMP_DEFINED(a,s)

#endif

#ifndef BYTE_ORDER

# if (defined(_LITTLE_ENDIAN) || defined(_BIG_ENDIAN)) && !(defined(_LITTLE_ENDIAN) && defined(_BIG_ENDIAN))

/* Solaris just defines one or the other */

# define LITTLE_ENDIAN 1234

# define BIG_ENDIAN 4321

# ifdef _LITTLE_ENDIAN

# define BYTE_ORDER LITTLE_ENDIAN

# else

# define BYTE_ORDER BIG_ENDIAN

# endif

# else

# define BYTE_ORDER __BYTE_ORDER

# endif

#endif

#ifndef LITTLE_ENDIAN

#define LITTLE_ENDIAN __LITTLE_ENDIAN

#endif

#ifndef BIG_ENDIAN

#define BIG_ENDIAN __BIG_ENDIAN

#endif

#if defined(__i386) || defined(__x86_64) || defined(_M_IX86)

#define MISALIGNED_OK 1

#endif

#include "lmdb.h"

#include "midl.h"

#if (BYTE_ORDER == LITTLE_ENDIAN) == (BYTE_ORDER == BIG_ENDIAN)

# error "Unknown or unsupported endianness (BYTE_ORDER)"

#elif (-6 & 5) || CHAR_BIT!=8 || UINT_MAX!=0xffffffff || MDB_SIZE_MAX%UINT_MAX

# error "Two's complement, reasonably sized integer types, please"

#endif

#if (((__clang_major__ << 8) | __clang_minor__) >= 0x0302) || (((__GNUC__ << 8) | __GNUC_MINOR__) >= 0x0403)

/** Mark infrequently used env functions as cold. This puts them in a separate

* section, and optimizes them for size */

#define ESECT __attribute__ ((cold))

#else

/* On older compilers, use a separate section */

# ifdef __GNUC__

# ifdef __APPLE__

# define ESECT __attribute__ ((section("__TEXT,text_env")))

# else

# define ESECT __attribute__ ((section("text_env")))

# endif

# else

# define ESECT

# endif

#endif

#ifdef _WIN32

#define CALL_CONV WINAPI

#else

#define CALL_CONV

#endif

/** @defgroup internal LMDB Internals

* @{

*/

/** @defgroup compat Compatibility Macros

* A bunch of macros to minimize the amount of platform-specific ifdefs

* needed throughout the rest of the code. When the features this library

* needs are similar enough to POSIX to be hidden in a one-or-two line

* replacement, this macro approach is used.

* @{

*/

/** Features under development */

#ifndef MDB_DEVEL

#define MDB_DEVEL 0

#endif

/** Wrapper around __func__, which is a C99 feature */

#if __STDC_VERSION__ >= 199901L

# define mdb_func_ __func__

#elif __GNUC__ >= 2 || _MSC_VER >= 1300

# define mdb_func_ __FUNCTION__

#else

/* If a debug message says <mdb_unknown>(), update the #if statements above */

# define mdb_func_ "<mdb_unknown>"

#endif

/* Internal error codes, not exposed outside liblmdb */

#define MDB_NO_ROOT (MDB_LAST_ERRCODE 10)

#ifdef _WIN32

#define MDB_OWNERDEAD ((int) WAIT_ABANDONED)

#elif defined MDB_USE_SYSV_SEM

#define MDB_OWNERDEAD (MDB_LAST_ERRCODE 11)

#elif defined(MDB_USE_POSIX_MUTEX) && defined(EOWNERDEAD)

#define MDB_OWNERDEAD EOWNERDEAD /**< #LOCK_MUTEX0() result if dead owner */

#endif

#ifdef __GLIBC__

#define GLIBC_VER ((__GLIBC__ << 16 )| __GLIBC_MINOR__)

#endif

/** Some platforms define the EOWNERDEAD error code

* even though they don't support Robust Mutexes.

* Compile with -DMDB_USE_ROBUST=0, or use some other

* mechanism like -DMDB_USE_SYSV_SEM instead of

* -DMDB_USE_POSIX_MUTEX. (SysV semaphores are

* also Robust, but some systems don't support them

* either.)

*/

#ifndef MDB_USE_ROBUST

/* Android currently lacks Robust Mutex support. So does glibc < 2.4. */

# if defined(MDB_USE_POSIX_MUTEX) && (defined(__ANDROID__) || \

(defined(__GLIBC__) && GLIBC_VER < 0x020004))

# define MDB_USE_ROBUST 0

# else

# define MDB_USE_ROBUST 1

# endif

#endif /* !MDB_USE_ROBUST */

#if defined(MDB_USE_POSIX_MUTEX) && (MDB_USE_ROBUST)

/* glibc < 2.12 only provided _np API */

# if (defined(__GLIBC__) && GLIBC_VER < 0x02000c) || \

(defined(PTHREAD_MUTEX_ROBUST_NP) && !defined(PTHREAD_MUTEX_ROBUST))

# define PTHREAD_MUTEX_ROBUST PTHREAD_MUTEX_ROBUST_NP

# define pthread_mutexattr_setrobust(attr, flag) pthread_mutexattr_setrobust_np(attr, flag)

# define pthread_mutex_consistent(mutex) pthread_mutex_consistent_np(mutex)

# endif

#endif /* MDB_USE_POSIX_MUTEX && MDB_USE_ROBUST */

#if defined(MDB_OWNERDEAD) && (MDB_USE_ROBUST)

#define MDB_ROBUST_SUPPORTED 1

#endif

#ifdef _WIN32

#define MDB_USE_HASH 1

#define MDB_PIDLOCK 0

#define THREAD_RET DWORD

#define pthread_t HANDLE

#define pthread_mutex_t HANDLE

#define pthread_cond_t HANDLE

typedef HANDLE mdb_mutex_t, mdb_mutexref_t;

#define pthread_key_t DWORD

#define pthread_self() GetCurrentThreadId()

#define pthread_key_create(x,y) \

((*(x) = TlsAlloc()) == TLS_OUT_OF_INDEXES ? ErrCode() : 0)

#define pthread_key_delete(x) TlsFree(x)

#define pthread_getspecific(x) TlsGetValue(x)

#define pthread_setspecific(x,y) (TlsSetValue(x,y) ? 0 : ErrCode())

#define pthread_mutex_unlock(x) ReleaseMutex(*x)

#define pthread_mutex_lock(x) WaitForSingleObject(*x, INFINITE)

#define pthread_cond_signal(x) SetEvent(*x)

#define pthread_cond_wait(cond,mutex) do{SignalObjectAndWait(*mutex, *cond, INFINITE, FALSE); WaitForSingleObject(*mutex, INFINITE);}while(0)

#define THREAD_CREATE(thr,start,arg) \

(((thr) = CreateThread(NULL, 0, start, arg, 0, NULL)) ? 0 : ErrCode())

#define THREAD_FINISH(thr) \

(WaitForSingleObject(thr, INFINITE) ? ErrCode() : 0)

#define LOCK_MUTEX0(mutex) WaitForSingleObject(mutex, INFINITE)

#define UNLOCK_MUTEX(mutex) ReleaseMutex(mutex)

#define mdb_mutex_consistent(mutex) 0

#define getpid() GetCurrentProcessId()

#define MDB_FDATASYNC(fd) (!FlushFileBuffers(fd))

#define MDB_MSYNC(addr,len,flags) (!FlushViewOfFile(addr,len))

#define ErrCode() GetLastError()

#define GET_PAGESIZE(x) {SYSTEM_INFO si; GetSystemInfo(&si); (x) = si.dwPageSize;}

#define close(fd) (CloseHandle(fd) ? 0 : -1)

#define munmap(ptr,len) UnmapViewOfFile(ptr)

#ifdef PROCESS_QUERY_LIMITED_INFORMATION

#define MDB_PROCESS_QUERY_LIMITED_INFORMATION PROCESS_QUERY_LIMITED_INFORMATION

#else

#define MDB_PROCESS_QUERY_LIMITED_INFORMATION 0x1000

#endif

#else

#define THREAD_RET void *

#define THREAD_CREATE(thr,start,arg) pthread_create(&thr,NULL,start,arg)

#define THREAD_FINISH(thr) pthread_join(thr,NULL)

/** For MDB_LOCK_FORMAT: True if readers take a pid lock in the lockfile */

#define MDB_PIDLOCK 1

#ifdef MDB_USE_POSIX_SEM

typedef sem_t *mdb_mutex_t, *mdb_mutexref_t;

#define LOCK_MUTEX0(mutex) mdb_sem_wait(mutex)

#define UNLOCK_MUTEX(mutex) sem_post(mutex)

static int

mdb_sem_wait(sem_t *sem)

{

int rc;

while ((rc = sem_wait(sem)) && (rc = errno) == EINTR) ;

return rc;

}

#elif defined MDB_USE_SYSV_SEM

typedef struct mdb_mutex {

} mdb_mutex_t[1], *mdb_mutexref_t;

#define LOCK_MUTEX0(mutex) mdb_sem_wait(mutex)

#define UNLOCK_MUTEX(mutex) do { \

struct sembuf sb = { 0, 1, SEM_UNDO }; \

sb.sem_num = (mutex)->semnum; \

*(mutex)->locked = 0; \

semop((mutex)->semid, &sb, 1); \

} while(0)

static int

mdb_sem_wait(mdb_mutexref_t sem)

{

int rc, *locked = sem->locked;

struct sembuf sb = { 0, -1, SEM_UNDO };

sb.sem_num = sem->semnum;

do {

if (!semop(sem->semid, &sb, 1)) {

rc = *locked ? MDB_OWNERDEAD : MDB_SUCCESS;

*locked = 1;

break;

}

} while ((rc = errno) == EINTR);

return rc;

}

#define mdb_mutex_consistent(mutex) 0

#else /* MDB_USE_POSIX_MUTEX: */

/** Shared mutex/semaphore as the original is stored.

*

* Not for copies. Instead it can be assigned to an #mdb_mutexref_t.

* When mdb_mutexref_t is a pointer and mdb_mutex_t is not, then it

* is array[size 1] so it can be assigned to the pointer.

*/

typedef pthread_mutex_t mdb_mutex_t[1];

/** Reference to an #mdb_mutex_t */

typedef pthread_mutex_t *mdb_mutexref_t;

/** Lock the reader or writer mutex.

* Returns 0 or a code to give #mdb_mutex_failed(), as in #LOCK_MUTEX().

*/

#define LOCK_MUTEX0(mutex) pthread_mutex_lock(mutex)

/** Unlock the reader or writer mutex.

*/

#define UNLOCK_MUTEX(mutex) pthread_mutex_unlock(mutex)

/** Mark mutex-protected data as repaired, after death of previous owner.

*/

#define mdb_mutex_consistent(mutex) pthread_mutex_consistent(mutex)

#endif /* MDB_USE_POSIX_SEM || MDB_USE_SYSV_SEM */

/** Get the error code for the last failed system function.

*/

#define ErrCode() errno

/** An abstraction for a file handle.

* On POSIX systems file handles are small integers. On Windows

* they're opaque pointers.

*/

#define HANDLE int

/** A value for an invalid file handle.

* Mainly used to initialize file variables and signify that they are

* unused.

*/

#define INVALID_HANDLE_VALUE (-1)

/** Get the size of a memory page for the system.

* This is the basic size that the platform's memory manager uses, and is

* fundamental to the use of memory-mapped files.

*/

#define GET_PAGESIZE(x) ((x) = sysconf(_SC_PAGE_SIZE))

#endif

#define Z MDB_FMT_Z /**< printf/scanf format modifier for size_t */

#define Yu MDB_PRIy(u) /**< printf format for #mdb_size_t */

#define Yd MDB_PRIy(d) /**< printf format for 'signed #mdb_size_t' */

#ifdef MDB_USE_SYSV_SEM

#define MNAME_LEN (sizeof(int))

#else

#define MNAME_LEN (sizeof(pthread_mutex_t))

#endif

/** Initial part of #MDB_env.me_mutexname[].

* Changes to this code must be reflected in #MDB_LOCK_FORMAT.

*/

#ifdef _WIN32

#define MUTEXNAME_PREFIX "Global\\MDB"

#elif defined MDB_USE_POSIX_SEM

#define MUTEXNAME_PREFIX "/MDB"

#endif

/** @} */

#ifdef MDB_ROBUST_SUPPORTED

/** Lock mutex, handle any error, set rc = result.

* Return 0 on success, nonzero (not rc) on error.

*/

#define LOCK_MUTEX(rc, env, mutex) \

(((rc) = LOCK_MUTEX0(mutex)) && \

((rc) = mdb_mutex_failed(env, mutex, rc)))

static int mdb_mutex_failed(MDB_env *env, mdb_mutexref_t mutex, int rc);

#else

#define LOCK_MUTEX(rc, env, mutex) ((rc) = LOCK_MUTEX0(mutex))

#define mdb_mutex_failed(env, mutex, rc) (rc)

#endif

#ifndef _WIN32

/** A flag for opening a file and requesting synchronous data writes.

* This is only used when writing a meta page. It's not strictly needed;

* we could just do a normal write and then immediately perform a flush.

* But if this flag is available it saves us an extra system call.

*

* @note If O_DSYNC is undefined but exists in /usr/include,

* preferably set some compiler flag to get the definition.

*/

#ifndef MDB_DSYNC

# ifdef O_DSYNC

# define MDB_DSYNC O_DSYNC

# else

# define MDB_DSYNC O_SYNC

# endif

#endif

#endif

/** Function for flushing the data of a file. Define this to fsync

* if fdatasync() is not supported.

*/

#ifndef MDB_FDATASYNC

# define MDB_FDATASYNC fdatasync

#endif

#ifndef MDB_MSYNC

# define MDB_MSYNC(addr,len,flags) msync(addr,len,flags)

#endif

#ifndef MS_SYNC

#define MS_SYNC 1

#endif

#ifndef MS_ASYNC

#define MS_ASYNC 0

#endif

/** A page number in the database.

* Note that 64 bit page numbers are overkill, since pages themselves

* already represent 12-13 bits of addressable memory, and the OS will

* always limit applications to a maximum of 63 bits of address space.

*

* @note In the #MDB_node structure, we only store 48 bits of this value,

* which thus limits us to only 60 bits of addressable data.

*/

typedef MDB_ID pgno_t;

/** A transaction ID.

* See struct MDB_txn.mt_txnid for details.

*/

typedef MDB_ID txnid_t;

/** @defgroup debug Debug Macros

* @{

*/

#ifndef MDB_DEBUG

/** Enable debug output. Needs variable argument macros (a C99 feature).

* Set this to 1 for copious tracing. Set to 2 to add dumps of all IDLs

* read from and written to the database (used for free space management).

*/

#define MDB_DEBUG 0

#endif

#if MDB_DEBUG

static int mdb_debug;

static txnid_t mdb_debug_start;

/** Print a debug message with printf formatting.

* Requires double parenthesis around 2 or more args.

*/

# define DPRINTF(args) ((void) ((mdb_debug) && DPRINTF0 args))

# define DPRINTF0(fmt, ...) \

fprintf(stderr, "%s:%d " fmt "\n", mdb_func_, __LINE__, __VA_ARGS__)

#else

# define DPRINTF(args) ((void) 0)

#endif

/** Print a debug string.

* The string is printed literally, with no format processing.

*/

#define DPUTS(arg) DPRINTF(("%s", arg))

/** Debugging output value of a cursor DBI: Negative in a sub-cursor. */

#define DDBI(mc) \

(((mc)->mc_flags & C_SUB) ? -(int)(mc)->mc_dbi : (int)(mc)->mc_dbi)

/** @} */

/** @brief The maximum size of a database page.

*

* It is 32k or 64k, since value-PAGEBASE must fit in

* #MDB_page.%mp_upper.

*

* LMDB will use database pages < OS pages if needed.

* That causes more I/O in write transactions: The OS must

* know (read) the whole page before writing a partial page.

*

* Note that we don't currently support Huge pages. On Linux,

* regular data files cannot use Huge pages, and in general

* Huge pages aren't actually pageable. We rely on the OS

* demand-pager to read our data and page it out when memory

* pressure from other processes is high. So until OSs have

* actual paging support for Huge pages, they're not viable.

*/

#define MAX_PAGESIZE (PAGEBASE ? 0x10000 : 0x8000)

/** The minimum number of keys required in a database page.

* Setting this to a larger value will place a smaller bound on the

* maximum size of a data item. Data items larger than this size will

* be pushed into overflow pages instead of being stored directly in

* the B-tree node. This value used to default to 4. With a page size

* of 4096 bytes that meant that any item larger than 1024 bytes would

* go into an overflow page. That also meant that on average 2-3KB of

* each overflow page was wasted space. The value cannot be lower than

* 2 because then there would no longer be a tree structure. With this

* value, items larger than 2KB will go into overflow pages, and on

* average only 1KB will be wasted.

*/

#define MDB_MINKEYS 2

/** A stamp that identifies a file as an LMDB file.

* There's nothing special about this value other than that it is easily

* recognizable, and it will reflect any byte order mismatches.

*/

#define MDB_MAGIC 0xBEEFC0DE

/** The version number for a database's datafile format. */

#define MDB_DATA_VERSION ((MDB_DEVEL) ? 999 : 1)

/** The version number for a database's lockfile format. */

#define MDB_LOCK_VERSION ((MDB_DEVEL) ? 999 : 2)

/** Number of bits representing #MDB_LOCK_VERSION in #MDB_LOCK_FORMAT.

* The remaining bits must leave room for #MDB_lock_desc.

*/

#define MDB_LOCK_VERSION_BITS 12

/** @brief The max size of a key we can write, or 0 for computed max.

*

* This macro should normally be left alone or set to 0.

* Note that a database with big keys or dupsort data cannot be

* reliably modified by a liblmdb which uses a smaller max.

* The default is 511 for backwards compat, or 0 when #MDB_DEVEL.

*

* Other values are allowed, for backwards compat. However:

* A value bigger than the computed max can break if you do not

* know what you are doing, and liblmdb <= 0.9.10 can break when

* modifying a DB with keys/dupsort data bigger than its max.

*

* Data items in an #MDB_DUPSORT database are also limited to

* this size, since they're actually keys of a sub-DB. Keys and

* #MDB_DUPSORT data items must fit on a node in a regular page.

*/

#ifndef MDB_MAXKEYSIZE

#define MDB_MAXKEYSIZE ((MDB_DEVEL) ? 0 : 511)

#endif

/** The maximum size of a key we can write to the environment. */

#if MDB_MAXKEYSIZE

#define ENV_MAXKEY(env) (MDB_MAXKEYSIZE)

#else

#define ENV_MAXKEY(env) ((env)->me_maxkey)

#endif

/** @brief The maximum size of a data item.

*

* We only store a 32 bit value for node sizes.

*/

#define MAXDATASIZE 0xffffffffUL

#if MDB_DEBUG

/** Key size which fits in a #DKBUF.

* @ingroup debug

*/

#define DKBUF_MAXKEYSIZE ((MDB_MAXKEYSIZE) > 0 ? (MDB_MAXKEYSIZE) : 511)

/** A key buffer.

* @ingroup debug

* This is used for printing a hex dump of a key's contents.

*/

#define DKBUF char kbuf[DKBUF_MAXKEYSIZE*2 1]

/** Display a key in hex.

* @ingroup debug

* Invoke a function to display a key in hex.

*/

#define DKEY(x) mdb_dkey(x, kbuf)

#else

#define DKBUF

#define DKEY(x) 0

#endif

/** An invalid page number.

* Mainly used to denote an empty tree.

*/

#define P_INVALID (~(pgno_t)0)

/** Test if the flags \b f are set in a flag word \b w. */

#define F_ISSET(w, f) (((w) & (f)) == (f))

/** Round \b n up to an even number. */

#define EVEN(n) (((n) 1U) & -2) /* sign-extending -2 to match n 1U */

/** Least significant 1-bit of \b n. n must be of an unsigned type. */

#define LOW_BIT(n) ((n) & (-(n)))

/** (log2(\b p2) % \b n), for p2 = power of 2 and 0 < n < 8. */

#define LOG2_MOD(p2, n) (7 - 86 / ((p2) % ((1U<<(n))-1) 11))

/* Explanation: Let p2 = 2**(n*y x), x<n and M = (1U<<n)-1. Now p2 =

* (M 1)**y * 2**x = 2**x (mod M). Finally "/" "happens" to return 7-x.

*/

/** Should be alignment of \b type. Ensure it is a power of 2. */

#define ALIGNOF2(type) \

LOW_BIT(offsetof(struct { char ch_; type align_; }, align_))

/** Used for offsets within a single page.

* Since memory pages are typically 4 or 8KB in size, 12-13 bits,

* this is plenty.

*/

typedef uint16_t indx_t;

typedef unsigned long long mdb_hash_t;

/** Default size of memory map.

* This is certainly too small for any actual applications. Apps should always set

* the size explicitly using #mdb_env_set_mapsize().

*/

#define DEFAULT_MAPSIZE 1048576

/** @defgroup readers Reader Lock Table

* Readers don't acquire any locks for their data access. Instead, they

* simply record their transaction ID in the reader table. The reader

* mutex is needed just to find an empty slot in the reader table. The

* slot's address is saved in thread-specific data so that subsequent read

* transactions started by the same thread need no further locking to proceed.

*

* If #MDB_NOTLS is set, the slot address is not saved in thread-specific data.

*

* No reader table is used if the database is on a read-only filesystem, or

* if #MDB_NOLOCK is set.

*

* Since the database uses multi-version concurrency control, readers don't

* actually need any locking. This table is used to keep track of which

* readers are using data from which old transactions, so that we'll know

* when a particular old transaction is no longer in use. Old transactions

* that have discarded any data pages can then have those pages reclaimed

* for use by a later write transaction.

*

* The lock table is constructed such that reader slots are aligned with the

* processor's cache line size. Any slot is only ever used by one thread.

* This alignment guarantees that there will be no contention or cache

* thrashing as threads update their own slot info, and also eliminates

* any need for locking when accessing a slot.

*

* A writer thread will scan every slot in the table to determine the oldest

* outstanding reader transaction. Any freed pages older than this will be

* reclaimed by the writer. The writer doesn't use any locks when scanning

* this table. This means that there's no guarantee that the writer will

* see the most up-to-date reader info, but that's not required for correct

* operation - all we need is to know the upper bound on the oldest reader,

* we don't care at all about the newest reader. So the only consequence of

* reading stale information here is that old pages might hang around a

* while longer before being reclaimed. That's actually good anyway, because

* the longer we delay reclaiming old pages, the more likely it is that a

* string of contiguous pages can be found after coalescing old pages from

* many old transactions together.

* @{

*/

/** Number of slots in the reader table.

* This value was chosen somewhat arbitrarily. 126 readers plus a

* couple mutexes fit exactly into 8KB on my development machine.

* Applications should set the table size using #mdb_env_set_maxreaders().

*/

#define DEFAULT_READERS 126

/** The size of a CPU cache line in bytes. We want our lock structures

* aligned to this size to avoid false cache line sharing in the

* lock table.

* This value works for most CPUs. For Itanium this should be 128.

*/

#ifndef CACHELINE

#define CACHELINE 64

#endif

/** The information we store in a single slot of the reader table.

* In addition to a transaction ID, we also record the process and

* thread ID that owns a slot, so that we can detect stale information,

* e.g. threads or processes that went away without cleaning up.

* @note We currently don't check for stale records. We simply re-init

* the table when we know that we're the only process opening the

* lock file.

*/

typedef struct MDB_rxbody {

} MDB_rxbody;

/** The actual reader record, with cacheline padding. */

typedef struct MDB_reader {

} MDB_reader;

/** The header for the reader table.

* The table resides in a memory-mapped file. (This is a different file

* than is used for the main database.)

*

* For POSIX the actual mutexes reside in the shared memory of this

* mapped file. On Windows, mutexes are named objects allocated by the

* kernel; we store the mutex names in this mapped file so that other

* processes can grab them. This same approach is also used on

* MacOSX/Darwin (using named semaphores) since MacOSX doesn't support

* process-shared POSIX mutexes. For these cases where a named object

* is used, the object name is derived from a 64 bit FNV hash of the

* environment pathname. As such, naming collisions are extremely

* unlikely. If a collision occurs, the results are unpredictable.

*/

typedef struct MDB_txbody {

} MDB_txbody;

/** The actual reader table definition. */

typedef struct MDB_txninfo {

} MDB_txninfo;

/** Lockfile format signature: version, features and field layout */

#define MDB_LOCK_FORMAT \

/** Lock type and layout. Values 0-119. _WIN32 implies #MDB_PIDLOCK.

* Some low values are reserved for future tweaks.

*/

#ifdef _WIN32

# define MDB_LOCK_TYPE (0 ALIGNOF2(mdb_hash_t)/8 % 2)

#elif defined MDB_USE_POSIX_SEM

# define MDB_LOCK_TYPE (4 ALIGNOF2(mdb_hash_t)/8 % 2)

#elif defined MDB_USE_SYSV_SEM

# define MDB_LOCK_TYPE (8)

#elif defined MDB_USE_POSIX_MUTEX

/* We do not know the inside of a POSIX mutex and how to check if mutexes

* used by two executables are compatible. Just check alignment and size.

*/

# define MDB_LOCK_TYPE (10 \

LOG2_MOD(ALIGNOF2(pthread_mutex_t), 5) \

sizeof(pthread_mutex_t) / 4U % 22 * 5)

#endif

enum {

/** Magic number for lockfile layout and features.

*

* This *attempts* to stop liblmdb variants compiled with conflicting

* options from using the lockfile at the same time and thus breaking

* it. It describes locking types, and sizes and sometimes alignment

* of the various lockfile items.

*

* The detected ranges are mostly guesswork, or based simply on how

* big they could be without using more bits. So we can tweak them

* in good conscience when updating #MDB_LOCK_VERSION.

*/

MDB_lock_desc =

/* Default CACHELINE=64 vs. other values (have seen mention of 32-256) */

(CACHELINE==64 ? 0 : 1 LOG2_MOD(CACHELINE >> (CACHELINE>64), 5))

6 * (sizeof(MDB_PID_T)/4 % 3) /* legacy(2) to word(4/8)? */

18 * (sizeof(pthread_t)/4 % 5) /* can be struct{id, active data} */

90 * (sizeof(MDB_txbody) / CACHELINE % 3)

270 * (MDB_LOCK_TYPE % 120)

/* The above is < 270*120 < 2**15 */

((sizeof(txnid_t) == 8) << 15) /* 32bit/64bit */

((sizeof(MDB_reader) > CACHELINE) << 16)

/* Not really needed - implied by MDB_LOCK_TYPE != (_WIN32 locking) */

(((MDB_PIDLOCK) != 0) << 17)

/* 18 bits total: Must be <= (32 - MDB_LOCK_VERSION_BITS). */

};

/** @} */

/** Common header for all page types. The page type depends on #mp_flags.

*

* #P_BRANCH and #P_LEAF pages have unsorted '#MDB_node's at the end, with

* sorted #mp_ptrs[] entries referring to them. Exception: #P_LEAF2 pages

* omit mp_ptrs and pack sorted #MDB_DUPFIXED values after the page header.

*

* #P_OVERFLOW records occupy one or more contiguous pages where only the

* first has a page header. They hold the real data of #F_BIGDATA nodes.

*

* #P_SUBP sub-pages are small leaf "pages" with duplicate data.

* A node with flag #F_DUPDATA but not #F_SUBDATA contains a sub-page.

* (Duplicate data can also go in sub-databases, which use normal pages.)

*

* #P_META pages contain #MDB_meta, the start point of an LMDB snapshot.

*

* Each non-metapage up to #MDB_meta.%mm_last_pg is reachable exactly once

* in the snapshot: Either used by a database or listed in a freeDB record.

*/

typedef struct MDB_page {