← Back to branch summary

~ubuntu-branches/ubuntu/raring/openldap/raring

« back to all changes in this revision

Viewing changes to libraries/libmdb/mdb.c

  • Committer: Package Import Robot
  • Author(s): James Page
  • Date: 2012-07-20 13:48:32 UTC
  • mfrom: (1.1.10) (0.3.20 sid)
  • Revision ID: package-import@ubuntu.com-20120720134832-943guojk7qlhtjzi
Tags: 2.4.31-1ubuntu1
https://launchpad.net/bugs/495418
https://launchpad.net/bugs/423246
https://launchpad.net/bugs/675391
https://launchpad.net/bugs/610544
https://launchpad.net/bugs/390579
* Merge from Debian unstable.  Remaining changes:
  - Enable AppArmor support:
    - d/apparmor-profile: add AppArmor profile
    - d/rules: use dh_apparmor
    - d/control: Build-Depends on dh-apparmor
    - d/slapd.README.Debian: add note about AppArmor
    - d/slapd.dirs: add etc/apparmor.d/force-complain
  - Enable GSSAPI support (LP: #495418):
    - d/patches/gssapi.diff, thanks to Jerry Carter (Likewise):
      - Add --with-gssapi support
      - Make guess_service_principal() more robust when determining
        principal
    - d/configure.options: Configure with --with-gssapi
    - d/control: Added libkrb5-dev as a build depend
  - Enable ufw support (LP: #423246):
    - d/control: suggest ufw.
    - d/rules: install ufw profile.
    - d/slapd.ufw.profile: add ufw profile.
  - Enable nss overlay (LP: #675391):
    - d/{patches/nssov-build,/rules}: Apply, build and package the
      nss overlay.
  - d/{rules,slapd.py}: Add apport hook. (LP: #610544)
  - d/slapd.init.ldif: don't set olcRootDN since it's not defined in
    either the default DIT nor via an Authn mapping.
  - d/slapd.scripts-common: 
    - add slapcat_opts to local variables.
    - Remove unused variable new_conf.
    - Fix backup directory naming for multiple reconfiguration.
  - d/{slapd.default,slapd.README.Debian}: use the new configuration style.
  - d/rules: Enable -DLDAP_CONNECTIONLESS to build CLDAP (UDP) support
    in the openldap library, as required by Likewise-Open (LP: #390579)
  - d/{control,rules}: enable PIE hardening
* Dropped changes:
  - d/patches/its-7107-fix-Operation-init-on-reuse.diff: Included in upstream release.
  - d/patches/CVE-2011-4079: Included in upstream release.
  - d/patches/service-operational-before-detach: Included in upstream release.
  - d/schema/extra/misc.ldif: Included upstream.
  - d/{rules,schema/extra}: Fix configure and clean rules to support
    extra schemas shipped as part of the debian/schema/ directory; no longer required.
  - Included in Debian:
    + Document cn=config in README file.
    + Install a default DIT; actually a minimal configuration.
    + d/patches/heimdal-fix.
* General tidy of d/patches to remove obsolete patches being held in Ubuntu delta.

Show diffs side-by-side

added added

removed removed

Lines of Context:
libraries/libmdb/mdb.c
5
5
 *      BerkeleyDB API, but much simplified.
6
6
 */
7
7
/*
8
 
 * Copyright 2011 Howard Chu, Symas Corp.
 
8
 * Copyright 2011-2012 Howard Chu, Symas Corp.
9
9
 * All rights reserved.
10
10
 *
11
11
 * Redistribution and use in source and binary forms, with or without
57
57
#include <time.h>
58
58
#include <unistd.h>
59
59
 
 
60
#if !(defined(BYTE_ORDER) || defined(__BYTE_ORDER))
 
61
#include <resolv.h>     /* defines BYTE_ORDER on HPUX and Solaris */
 
62
#endif
 
63
 
60
64
#ifndef _WIN32
61
65
#include <pthread.h>
62
66
#ifdef __APPLE__
64
68
#endif
65
69
#endif
66
70
 
 
71
#ifdef USE_VALGRIND
 
72
#include <valgrind/memcheck.h>
 
73
#define VGMEMP_CREATE(h,r,z)    VALGRIND_CREATE_MEMPOOL(h,r,z)
 
74
#define VGMEMP_ALLOC(h,a,s) VALGRIND_MEMPOOL_ALLOC(h,a,s)
 
75
#define VGMEMP_FREE(h,a) VALGRIND_MEMPOOL_FREE(h,a)
 
76
#define VGMEMP_DESTROY(h)       VALGRIND_DESTROY_MEMPOOL(h)
 
77
#define VGMEMP_DEFINED(a,s)     VALGRIND_MAKE_MEM_DEFINED(a,s)
 
78
#else
 
79
#define VGMEMP_CREATE(h,r,z)
 
80
#define VGMEMP_ALLOC(h,a,s)
 
81
#define VGMEMP_FREE(h,a)
 
82
#define VGMEMP_DESTROY(h)
 
83
#define VGMEMP_DEFINED(a,s)
 
84
#endif
 
85
 
67
86
#ifndef BYTE_ORDER
68
87
# if (defined(_LITTLE_ENDIAN) || defined(_BIG_ENDIAN)) && !(defined(_LITTLE_ENDIAN) && defined(_BIG_ENDIAN))
69
88
/* Solaris just defines one or the other */
183
202
 
184
203
#if defined(_WIN32) || defined(__APPLE__)
185
204
#define MNAME_LEN       32
 
205
#else
 
206
#define MNAME_LEN       (sizeof(pthread_mutex_t))
186
207
#endif
187
208
 
188
209
/** @} */
238
259
#if !(__STDC_VERSION__ >= 199901L || defined(__GNUC__))
239
260
# define DPRINTF        (void)  /* Vararg macros may be unsupported */
240
261
#elif MDB_DEBUG
 
262
static int mdb_debug;
 
263
static int mdb_debug_start;
 
264
 
241
265
        /**     Print a debug message with printf formatting. */
242
266
# define DPRINTF(fmt, ...)      /**< Requires 2 or more args */ \
243
 
        fprintf(stderr, "%s:%d " fmt "\n", __func__, __LINE__, __VA_ARGS__)
 
267
        if (mdb_debug) fprintf(stderr, "%s:%d " fmt "\n", __func__, __LINE__, __VA_ARGS__)
244
268
#else
245
269
# define DPRINTF(fmt, ...)      ((void) 0)
246
270
#endif
311
335
#endif
312
336
 
313
337
/**     @defgroup lazylock      Lazy Locking
314
 
 *      Macros for locks that are't actually needed.
 
338
 *      Macros for locks that aren't actually needed.
315
339
 *      The DB view is always consistent because all writes are wrapped in
316
340
 *      the wmutex. Finer-grained locks aren't necessary.
317
341
 *      @{
473
497
         *      unlikely. If a collision occurs, the results are unpredictable.
474
498
         */
475
499
typedef struct MDB_txbody {
476
 
                /** Stamp identifying this as an MDB lock file. It must be set
 
500
                /** Stamp identifying this as an MDB file. It must be set
477
501
                 *      to #MDB_MAGIC. */
478
502
        uint32_t        mtb_magic;
479
503
                /** Version number of this lock file. Must be set to #MDB_VERSION. */
524
548
                pthread_mutex_t mt2_wmutex;
525
549
#define mti_wmutex      mt2.mt2_wmutex
526
550
#endif
527
 
                char pad[(sizeof(pthread_mutex_t)+CACHELINE-1) & ~(CACHELINE-1)];
 
551
                char pad[(MNAME_LEN+CACHELINE-1) & ~(CACHELINE-1)];
528
552
        } mt2;
529
553
        MDB_reader      mti_readers[1];
530
554
} MDB_txninfo;
729
753
 
730
754
        /** Meta page content. */
731
755
typedef struct MDB_meta {
732
 
                /** Stamp identifying this as an MDB data file. It must be set
 
756
                /** Stamp identifying this as an MDB file. It must be set
733
757
                 *      to #MDB_MAGIC. */
734
758
        uint32_t        mm_magic;
735
759
                /** Version number of this lock file. Must be set to #MDB_VERSION. */
745
769
        txnid_t         mm_txnid;                       /**< txnid that committed this page */
746
770
} MDB_meta;
747
771
 
 
772
        /** Buffer for a stack-allocated dirty page.
 
773
         *      The members define size and alignment, and silence type
 
774
         *      aliasing warnings.  They are not used directly; that could
 
775
         *      mean incorrectly using several union members in parallel.
 
776
         */
 
777
typedef union MDB_pagebuf {
 
778
        char            mb_raw[MDB_PAGESIZE];
 
779
        MDB_page        mb_page;
 
780
        struct {
 
781
                char            mm_pad[PAGEHDRSZ];
 
782
                MDB_meta        mm_meta;
 
783
        } mb_metabuf;
 
784
} MDB_pagebuf;
 
785
 
748
786
        /** Auxiliary DB info.
749
787
         *      The information here is mostly static/read-only. There is
750
788
         *      only a single copy of this record in the environment.
838
876
        /** The @ref mt_dbflag for this database */
839
877
        unsigned char   *mc_dbflag;
840
878
        unsigned short  mc_snum;        /**< number of pushed pages */
841
 
        unsigned short  mc_top;         /**< index of top page, mc_snum-1 */
 
879
        unsigned short  mc_top;         /**< index of top page, normally mc_snum-1 */
842
880
/** @defgroup mdb_cursor        Cursor Flags
843
881
 *      @ingroup internal
844
882
 *      Cursor state flags.
906
944
        unsigned int    me_psize;       /**< size of a page, from #GET_PAGESIZE */
907
945
        unsigned int    me_db_toggle;   /**< which DB table is current */
908
946
        txnid_t         me_wtxnid;              /**< ID of last txn we committed */
 
947
        txnid_t         me_pgfirst;             /**< ID of first old page record we used */
 
948
        txnid_t         me_pglast;              /**< ID of last old page record we used */
909
949
        MDB_dbx         *me_dbxs;               /**< array of static DB info */
910
950
        MDB_db          *me_dbs[2];             /**< two arrays of MDB_db info */
911
951
        MDB_oldpages *me_pghead;        /**< list of old page records */
928
968
};
929
969
        /** max number of pages to commit in one writev() call */
930
970
#define MDB_COMMIT_PAGES         64
 
971
#if defined(IOV_MAX) && IOV_MAX < MDB_COMMIT_PAGES
 
972
#undef MDB_COMMIT_PAGES
 
973
#define MDB_COMMIT_PAGES        IOV_MAX
 
974
#endif
931
975
 
932
976
static MDB_page *mdb_page_alloc(MDB_cursor *mc, int num);
933
977
static MDB_page *mdb_page_new(MDB_cursor *mc, uint32_t flags, int num);
1038
1082
         * printable characters, print it as-is instead of converting to hex.
1039
1083
         */
1040
1084
#if 1
 
1085
        buf[0] = '\0';
1041
1086
        for (i=0; i<key->mv_size; i++)
1042
1087
                ptr += sprintf(ptr, "%02x", *c++);
1043
1088
#else
1045
1090
#endif
1046
1091
        return buf;
1047
1092
}
 
1093
 
 
1094
/** Display all the keys in the page. */
 
1095
static void
 
1096
mdb_page_keys(MDB_page *mp)
 
1097
{
 
1098
        MDB_node *node;
 
1099
        unsigned int i, nkeys;
 
1100
        MDB_val key;
 
1101
        DKBUF;
 
1102
 
 
1103
        nkeys = NUMKEYS(mp);
 
1104
        DPRINTF("numkeys %d", nkeys);
 
1105
        for (i=0; i<nkeys; i++) {
 
1106
                node = NODEPTR(mp, i);
 
1107
                key.mv_size = node->mn_ksize;
 
1108
                key.mv_data = node->mn_data;
 
1109
                DPRINTF("key %d: %s", i, DKEY(&key));
 
1110
        }
 
1111
}
 
1112
#endif
 
1113
 
 
1114
#if MDB_DEBUG > 2
 
1115
/** Count all the pages in each DB and in the freelist
 
1116
 *  and make sure it matches the actual number of pages
 
1117
 *  being used.
 
1118
 */
 
1119
static void mdb_audit(MDB_txn *txn)
 
1120
{
 
1121
        MDB_cursor mc;
 
1122
        MDB_val key, data;
 
1123
        int rc, i;
 
1124
        ID freecount, count;
 
1125
 
 
1126
        freecount = 0;
 
1127
        mdb_cursor_init(&mc, txn, FREE_DBI, NULL);
 
1128
        while ((rc = mdb_cursor_get(&mc, &key, &data, MDB_NEXT)) == 0)
 
1129
                freecount += *(ID *)data.mv_data;
 
1130
        freecount += txn->mt_dbs[0].md_branch_pages + txn->mt_dbs[0].md_leaf_pages +
 
1131
                txn->mt_dbs[0].md_overflow_pages;
 
1132
 
 
1133
        count = 0;
 
1134
        for (i = 0; i<txn->mt_numdbs; i++) {
 
1135
                count += txn->mt_dbs[i].md_branch_pages +
 
1136
                        txn->mt_dbs[i].md_leaf_pages +
 
1137
                        txn->mt_dbs[i].md_overflow_pages;
 
1138
                if (txn->mt_dbs[i].md_flags & MDB_DUPSORT) {
 
1139
                        MDB_xcursor mx;
 
1140
                        mdb_cursor_init(&mc, txn, i, &mx);
 
1141
                        mdb_page_search(&mc, NULL, 0);
 
1142
                        do {
 
1143
                                int j;
 
1144
                                MDB_page *mp;
 
1145
                                mp = mc.mc_pg[mc.mc_top];
 
1146
                                for (j=0; j<NUMKEYS(mp); j++) {
 
1147
                                        MDB_node *leaf = NODEPTR(mp, j);
 
1148
                                        if (leaf->mn_flags & F_SUBDATA) {
 
1149
                                                MDB_db db;
 
1150
                                                memcpy(&db, NODEDATA(leaf), sizeof(db));
 
1151
                                                count += db.md_branch_pages + db.md_leaf_pages +
 
1152
                                                        db.md_overflow_pages;
 
1153
                                        }
 
1154
                                }
 
1155
                        }
 
1156
                        while (mdb_cursor_sibling(&mc, 1) == 0);
 
1157
                }
 
1158
        }
 
1159
        assert(freecount + count + 2 >= txn->mt_next_pgno - 1);
 
1160
}
1048
1161
#endif
1049
1162
 
1050
1163
int
1068
1181
static MDB_page *
1069
1182
mdb_page_malloc(MDB_cursor *mc) {
1070
1183
        MDB_page *ret;
1071
 
        if (mc->mc_txn->mt_env->me_dpages) {
1072
 
                ret = mc->mc_txn->mt_env->me_dpages;
 
1184
        size_t sz = mc->mc_txn->mt_env->me_psize;
 
1185
        if ((ret = mc->mc_txn->mt_env->me_dpages) != NULL) {
 
1186
                VGMEMP_ALLOC(mc->mc_txn->mt_env, ret, sz);
 
1187
                VGMEMP_DEFINED(ret, sizeof(ret->mp_next));
1073
1188
                mc->mc_txn->mt_env->me_dpages = ret->mp_next;
1074
 
        } else {
1075
 
                ret = malloc(mc->mc_txn->mt_env->me_psize);
 
1189
        } else if ((ret = malloc(sz)) != NULL) {
 
1190
                VGMEMP_ALLOC(mc->mc_txn->mt_env, ret, sz);
1076
1191
        }
1077
1192
        return ret;
1078
1193
}
1096
1211
 
1097
1212
        if (txn->mt_txnid > 2) {
1098
1213
 
1099
 
                if (!txn->mt_env->me_pghead && mc->mc_dbi != FREE_DBI &&
 
1214
                if (!txn->mt_env->me_pghead &&
1100
1215
                        txn->mt_dbs[FREE_DBI].md_root != P_INVALID) {
1101
1216
                        /* See if there's anything in the free DB */
1102
1217
                        MDB_cursor m2;
1103
1218
                        MDB_node *leaf;
1104
 
                        txnid_t *kptr, oldest;
 
1219
                        MDB_val data;
 
1220
                        txnid_t *kptr, oldest, last;
1105
1221
 
1106
1222
                        mdb_cursor_init(&m2, txn, FREE_DBI, NULL);
1107
 
                        mdb_page_search(&m2, NULL, 0);
1108
 
                        leaf = NODEPTR(m2.mc_pg[m2.mc_top], 0);
1109
 
                        kptr = (txnid_t *)NODEKEY(leaf);
 
1223
                        if (!txn->mt_env->me_pgfirst) {
 
1224
                                mdb_page_search(&m2, NULL, 0);
 
1225
                                leaf = NODEPTR(m2.mc_pg[m2.mc_top], 0);
 
1226
                                kptr = (txnid_t *)NODEKEY(leaf);
 
1227
                                last = *kptr;
 
1228
                        } else {
 
1229
                                MDB_val key;
 
1230
                                int rc, exact;
 
1231
again:
 
1232
                                exact = 0;
 
1233
                                last = txn->mt_env->me_pglast + 1;
 
1234
                                leaf = NULL;
 
1235
                                key.mv_data = &last;
 
1236
                                key.mv_size = sizeof(last);
 
1237
                                rc = mdb_cursor_set(&m2, &key, &data, MDB_SET, &exact);
 
1238
                                if (rc)
 
1239
                                        goto none;
 
1240
                                last = *(txnid_t *)key.mv_data;
 
1241
                        }
1110
1242
 
1111
1243
                        {
1112
1244
                                unsigned int i;
1118
1250
                                }
1119
1251
                        }
1120
1252
 
1121
 
                        if (oldest > *kptr) {
 
1253
                        if (oldest > last) {
1122
1254
                                /* It's usable, grab it.
1123
1255
                                 */
1124
1256
                                MDB_oldpages *mop;
1125
 
                                MDB_val data;
1126
1257
                                pgno_t *idl;
1127
1258
 
1128
 
                                mdb_node_read(txn, leaf, &data);
 
1259
                                if (!txn->mt_env->me_pgfirst) {
 
1260
                                        mdb_node_read(txn, leaf, &data);
 
1261
                                }
 
1262
                                txn->mt_env->me_pglast = last;
 
1263
                                if (!txn->mt_env->me_pgfirst)
 
1264
                                        txn->mt_env->me_pgfirst = last;
1129
1265
                                idl = (ID *) data.mv_data;
 
1266
                                /* We might have a zero-length IDL due to freelist growth
 
1267
                                 * during a prior commit
 
1268
                                 */
 
1269
                                if (!idl[0]) goto again;
1130
1270
                                mop = malloc(sizeof(MDB_oldpages) + MDB_IDL_SIZEOF(idl) - sizeof(pgno_t));
1131
1271
                                mop->mo_next = txn->mt_env->me_pghead;
1132
 
                                mop->mo_txnid = *kptr;
 
1272
                                mop->mo_txnid = last;
1133
1273
                                txn->mt_env->me_pghead = mop;
1134
1274
                                memcpy(mop->mo_pages, idl, MDB_IDL_SIZEOF(idl));
1135
1275
 
1143
1283
                                        }
1144
1284
                                }
1145
1285
#endif
1146
 
                                /* drop this IDL from the DB */
1147
 
                                m2.mc_ki[m2.mc_top] = 0;
1148
 
                                m2.mc_flags = C_INITIALIZED;
1149
 
                                mdb_cursor_del(&m2, 0);
1150
1286
                        }
1151
1287
                }
 
1288
none:
1152
1289
                if (txn->mt_env->me_pghead) {
1153
1290
                        MDB_oldpages *mop = txn->mt_env->me_pghead;
1154
1291
                        if (num > 1) {
1184
1321
        }
1185
1322
        if (txn->mt_env->me_dpages && num == 1) {
1186
1323
                np = txn->mt_env->me_dpages;
 
1324
                VGMEMP_ALLOC(txn->mt_env, np, txn->mt_env->me_psize);
 
1325
                VGMEMP_DEFINED(np, sizeof(np->mp_next));
1187
1326
                txn->mt_env->me_dpages = np->mp_next;
1188
1327
        } else {
1189
 
                if ((np = malloc(txn->mt_env->me_psize * num )) == NULL)
 
1328
                size_t sz = txn->mt_env->me_psize * num;
 
1329
                if ((np = malloc(sz)) == NULL)
1190
1330
                        return NULL;
 
1331
                VGMEMP_ALLOC(txn->mt_env, np, sz);
1191
1332
        }
1192
1333
        if (pgno == P_INVALID) {
1193
1334
                np->mp_pgno = txn->mt_next_pgno;
1234
1375
                        for (m2 = mc->mc_txn->mt_cursors[dbi]; m2; m2=m2->mc_next) {
1235
1376
                                if (m2 == mc) continue;
1236
1377
                                m3 = &m2->mc_xcursor->mx_cursor;
 
1378
                                if (m3->mc_snum < mc->mc_snum) continue;
1237
1379
                                if (m3->mc_pg[mc->mc_top] == mc->mc_pg[mc->mc_top]) {
1238
1380
                                        m3->mc_pg[mc->mc_top] = mp;
1239
1381
                                }
1242
1384
                        MDB_cursor *m2;
1243
1385
 
1244
1386
                        for (m2 = mc->mc_txn->mt_cursors[mc->mc_dbi]; m2; m2=m2->mc_next) {
1245
 
                                if (m2 == mc) continue;
 
1387
                                if (m2 == mc || m2->mc_snum < mc->mc_snum) continue;
1246
1388
                                if (m2->mc_pg[mc->mc_top] == mc->mc_pg[mc->mc_top]) {
1247
1389
                                        m2->mc_pg[mc->mc_top] = mp;
1248
1390
                                }
1437
1579
                if (env->me_wtxnid < txn->mt_txnid)
1438
1580
                        mt_dbflag = DB_STALE;
1439
1581
                txn->mt_txnid++;
 
1582
#if MDB_DEBUG
 
1583
                if (txn->mt_txnid == mdb_debug_start)
 
1584
                        mdb_debug = 1;
 
1585
#endif
1440
1586
                txn->mt_toggle = env->me_txns->mti_me_toggle;
1441
1587
                txn->mt_u.dirty_list = env->me_dirty_list;
1442
1588
                txn->mt_u.dirty_list[0].mid = 0;
1589
1735
                        dp = txn->mt_u.dirty_list[i].mptr;
1590
1736
                        if (!IS_OVERFLOW(dp) || dp->mp_pages == 1) {
1591
1737
                                dp->mp_next = txn->mt_env->me_dpages;
 
1738
                                VGMEMP_FREE(txn->mt_env, dp);
1592
1739
                                txn->mt_env->me_dpages = dp;
1593
1740
                        } else {
1594
1741
                                /* large pages just get freed directly */
 
1742
                                VGMEMP_FREE(txn->mt_env, dp);
1595
1743
                                free(dp);
1596
1744
                        }
1597
1745
                }
1610
1758
                        txn->mt_env->me_pghead = mop->mo_next;
1611
1759
                        free(mop);
1612
1760
                }
 
1761
                txn->mt_env->me_pgfirst = 0;
 
1762
                txn->mt_env->me_pglast = 0;
1613
1763
 
1614
1764
                env->me_txn = NULL;
1615
1765
                /* The writer mutex was locked in mdb_txn_begin. */
1656
1806
        off_t            size;
1657
1807
        MDB_page        *dp;
1658
1808
        MDB_env *env;
1659
 
        pgno_t  next;
 
1809
        pgno_t  next, freecnt;
1660
1810
        MDB_cursor mc;
1661
1811
 
1662
1812
        assert(txn != NULL);
1736
1886
                }
1737
1887
                x = dst[0].mid;
1738
1888
                for (; y<=src[0].mid; y++) {
1739
 
                        if (++x >= MDB_IDL_UM_MAX)
 
1889
                        if (++x >= MDB_IDL_UM_MAX) {
 
1890
                                mdb_txn_abort(txn);
1740
1891
                                return ENOMEM;
 
1892
                        }
1741
1893
                        dst[x] = src[y];
1742
1894
                }
1743
1895
                dst[0].mid = x;
1766
1918
                /* make sure first page of freeDB is touched and on freelist */
1767
1919
                mdb_page_search(&mc, NULL, 1);
1768
1920
        }
 
1921
 
 
1922
        /* Delete IDLs we used from the free list */
 
1923
        if (env->me_pgfirst) {
 
1924
                txnid_t cur;
 
1925
                MDB_val key;
 
1926
                int exact = 0;
 
1927
 
 
1928
                key.mv_size = sizeof(cur);
 
1929
                for (cur = env->me_pgfirst; cur <= env->me_pglast; cur++) {
 
1930
                        key.mv_data = &cur;
 
1931
 
 
1932
                        mdb_cursor_set(&mc, &key, NULL, MDB_SET, &exact);
 
1933
                        mdb_cursor_del(&mc, 0);
 
1934
                }
 
1935
                env->me_pgfirst = 0;
 
1936
                env->me_pglast = 0;
 
1937
        }
 
1938
 
1769
1939
        /* save to free list */
 
1940
free2:
 
1941
        freecnt = txn->mt_free_pgs[0];
1770
1942
        if (!MDB_IDL_IS_ZERO(txn->mt_free_pgs)) {
1771
1943
                MDB_val key, data;
1772
 
                pgno_t i;
1773
1944
 
1774
1945
                /* make sure last page of freeDB is touched and on freelist */
1775
1946
                key.mv_size = MAXKEYSIZE+1;
1797
1968
                 * and make sure the entire thing got written.
1798
1969
                 */
1799
1970
                do {
1800
 
                        i = txn->mt_free_pgs[0];
 
1971
                        freecnt = txn->mt_free_pgs[0];
1801
1972
                        data.mv_size = MDB_IDL_SIZEOF(txn->mt_free_pgs);
1802
1973
                        rc = mdb_cursor_put(&mc, &key, &data, 0);
1803
1974
                        if (rc) {
1804
1975
                                mdb_txn_abort(txn);
1805
1976
                                return rc;
1806
1977
                        }
1807
 
                } while (i != txn->mt_free_pgs[0]);
1808
 
                if (mdb_midl_shrink(&txn->mt_free_pgs))
1809
 
                        env->me_free_pgs = txn->mt_free_pgs;
 
1978
                } while (freecnt != txn->mt_free_pgs[0]);
1810
1979
        }
1811
1980
        /* should only be one record now */
 
1981
again:
1812
1982
        if (env->me_pghead) {
1813
1983
                MDB_val key, data;
1814
1984
                MDB_oldpages *mop;
 
1985
                pgno_t orig;
 
1986
                txnid_t id;
1815
1987
 
1816
1988
                mop = env->me_pghead;
1817
 
                env->me_pghead = NULL;
1818
 
                key.mv_size = sizeof(pgno_t);
1819
 
                key.mv_data = &mop->mo_txnid;
 
1989
                id = mop->mo_txnid;
 
1990
                key.mv_size = sizeof(id);
 
1991
                key.mv_data = &id;
1820
1992
                data.mv_size = MDB_IDL_SIZEOF(mop->mo_pages);
1821
1993
                data.mv_data = mop->mo_pages;
 
1994
                orig = mop->mo_pages[0];
 
1995
                /* These steps may grow the freelist again
 
1996
                 * due to freed overflow pages...
 
1997
                 */
1822
1998
                mdb_cursor_put(&mc, &key, &data, 0);
1823
 
                free(mop);
 
1999
                if (mop == env->me_pghead && env->me_pghead->mo_txnid == id) {
 
2000
                        /* could have been used again here */
 
2001
                        if (mop->mo_pages[0] != orig) {
 
2002
                                data.mv_size = MDB_IDL_SIZEOF(mop->mo_pages);
 
2003
                                data.mv_data = mop->mo_pages;
 
2004
                                id = mop->mo_txnid;
 
2005
                                mdb_cursor_put(&mc, &key, &data, 0);
 
2006
                        }
 
2007
                        env->me_pghead = NULL;
 
2008
                        free(mop);
 
2009
                } else {
 
2010
                        /* was completely used up */
 
2011
                        mdb_cursor_del(&mc, 0);
 
2012
                        if (env->me_pghead)
 
2013
                                goto again;
 
2014
                }
 
2015
                env->me_pgfirst = 0;
 
2016
                env->me_pglast = 0;
 
2017
        }
 
2018
        /* Check for growth of freelist again */
 
2019
        if (freecnt != txn->mt_free_pgs[0])
 
2020
                goto free2;
 
2021
 
 
2022
        if (!MDB_IDL_IS_ZERO(txn->mt_free_pgs)) {
 
2023
                if (mdb_midl_shrink(&txn->mt_free_pgs))
 
2024
                        env->me_free_pgs = txn->mt_free_pgs;
1824
2025
        }
1825
2026
 
1826
2027
        /* Update DB root pointers. Their pages have already been
1839
2040
                        }
1840
2041
                }
1841
2042
        }
 
2043
#if MDB_DEBUG > 2
 
2044
        mdb_audit(txn);
 
2045
#endif
1842
2046
 
1843
2047
        /* Commit up to MDB_COMMIT_PAGES dirty pages to disk until done.
1844
2048
         */
1885
2089
                        dp = txn->mt_u.dirty_list[i].mptr;
1886
2090
                        if (dp->mp_pgno != next) {
1887
2091
                                if (n) {
1888
 
                                        DPRINTF("committing %u dirty pages", n);
1889
2092
                                        rc = writev(env->me_fd, iov, n);
1890
2093
                                        if (rc != size) {
1891
2094
                                                n = ErrCode();
1920
2123
                if (n == 0)
1921
2124
                        break;
1922
2125
 
1923
 
                DPRINTF("committing %u dirty pages", n);
1924
2126
                rc = writev(env->me_fd, iov, n);
1925
2127
                if (rc != size) {
1926
2128
                        n = ErrCode();
1940
2142
                dp = txn->mt_u.dirty_list[i].mptr;
1941
2143
                if (!IS_OVERFLOW(dp) || dp->mp_pages == 1) {
1942
2144
                        dp->mp_next = txn->mt_env->me_dpages;
 
2145
                        VGMEMP_FREE(txn->mt_env, dp);
1943
2146
                        txn->mt_env->me_dpages = dp;
1944
2147
                } else {
 
2148
                        VGMEMP_FREE(txn->mt_env, dp);
1945
2149
                        free(dp);
1946
2150
                }
1947
2151
                txn->mt_u.dirty_list[i].mid = 0;
1992
2196
static int
1993
2197
mdb_env_read_header(MDB_env *env, MDB_meta *meta)
1994
2198
{
1995
 
        char             page[MDB_PAGESIZE];
 
2199
        MDB_pagebuf     pbuf;
1996
2200
        MDB_page        *p;
1997
2201
        MDB_meta        *m;
1998
2202
        int              rc, err;
2001
2205
         */
2002
2206
 
2003
2207
#ifdef _WIN32
2004
 
        if (!ReadFile(env->me_fd, page, MDB_PAGESIZE, (DWORD *)&rc, NULL) || rc == 0)
 
2208
        if (!ReadFile(env->me_fd, &pbuf, MDB_PAGESIZE, (DWORD *)&rc, NULL) || rc == 0)
2005
2209
#else
2006
 
        if ((rc = read(env->me_fd, page, MDB_PAGESIZE)) == 0)
 
2210
        if ((rc = read(env->me_fd, &pbuf, MDB_PAGESIZE)) == 0)
2007
2211
#endif
2008
2212
        {
2009
2213
                return ENOENT;
2016
2220
                return err;
2017
2221
        }
2018
2222
 
2019
 
        p = (MDB_page *)page;
 
2223
        p = (MDB_page *)&pbuf;
2020
2224
 
2021
2225
        if (!F_ISSET(p->mp_flags, P_META)) {
2022
2226
                DPRINTF("page %zu not a meta page", p->mp_pgno);
2218
2422
        e->me_fd = INVALID_HANDLE_VALUE;
2219
2423
        e->me_lfd = INVALID_HANDLE_VALUE;
2220
2424
        e->me_mfd = INVALID_HANDLE_VALUE;
 
2425
        VGMEMP_CREATE(e,0,0);
2221
2426
        *env = e;
2222
2427
        return MDB_SUCCESS;
2223
2428
}
2316
2521
                i |= MAP_FIXED;
2317
2522
        env->me_map = mmap(meta.mm_address, env->me_mapsize, PROT_READ, i,
2318
2523
                env->me_fd, 0);
2319
 
        if (env->me_map == MAP_FAILED)
 
2524
        if (env->me_map == MAP_FAILED) {
 
2525
                env->me_map = NULL;
2320
2526
                return ErrCode();
 
2527
        }
2321
2528
#endif
2322
2529
 
2323
2530
        if (newenv) {
2566
2773
                size = rsize - sizeof(MDB_txninfo);
2567
2774
                env->me_maxreaders = size/sizeof(MDB_reader) + 1;
2568
2775
        }
 
2776
        {
2569
2777
#ifdef _WIN32
2570
 
        {
2571
2778
                HANDLE mh;
2572
2779
                mh = CreateFileMapping(env->me_lfd, NULL, PAGE_READWRITE,
2573
2780
                        0, 0, NULL);
2581
2788
                        rc = ErrCode();
2582
2789
                        goto fail;
2583
2790
                }
2584
 
        }
2585
2791
#else
2586
 
        env->me_txns = (MDB_txninfo *)mmap(0, rsize, PROT_READ|PROT_WRITE, MAP_SHARED,
2587
 
                env->me_lfd, 0);
2588
 
        if (env->me_txns == MAP_FAILED) {
2589
 
                rc = ErrCode();
2590
 
                goto fail;
2591
 
        }
 
2792
                void *m = mmap(NULL, rsize, PROT_READ|PROT_WRITE, MAP_SHARED,
 
2793
                        env->me_lfd, 0);
 
2794
                if (m == MAP_FAILED) {
 
2795
                        env->me_txns = NULL;
 
2796
                        rc = ErrCode();
 
2797
                        goto fail;
 
2798
                }
 
2799
                env->me_txns = m;
2592
2800
#endif
 
2801
        }
2593
2802
        if (*excl) {
2594
2803
#ifdef _WIN32
2595
2804
                char hexbuf[17];
2824
3033
        if (env == NULL)
2825
3034
                return;
2826
3035
 
 
3036
        VGMEMP_DESTROY(env);
2827
3037
        while (env->me_dpages) {
2828
3038
                dp = env->me_dpages;
 
3039
                VGMEMP_DEFINED(&dp->mp_next, sizeof(dp->mp_next));
2829
3040
                env->me_dpages = dp->mp_next;
2830
3041
                free(dp);
2831
3042
        }
3935
4146
        unsigned int mcount = 0;
3936
4147
        size_t nsize;
3937
4148
        int rc, rc2;
3938
 
        char pbuf[MDB_PAGESIZE];
 
4149
        MDB_pagebuf pbuf;
3939
4150
        char dbuf[MAXKEYSIZE+1];
3940
4151
        unsigned int nflags;
3941
4152
        DKBUF;
4031
4242
                                /* create a fake page for the dup items */
4032
4243
                                memcpy(dbuf, dkey.mv_data, dkey.mv_size);
4033
4244
                                dkey.mv_data = dbuf;
4034
 
                                fp = (MDB_page *)pbuf;
 
4245
                                fp = (MDB_page *)&pbuf;
4035
4246
                                fp->mp_pgno = mc->mc_pg[mc->mc_top]->mp_pgno;
4036
4247
                                fp->mp_flags = P_LEAF|P_DIRTY|P_SUBP;
4037
4248
                                fp->mp_lower = PAGEHDRSZ;
4047
4258
                                do_sub = 1;
4048
4259
                                rdata = &xdata;
4049
4260
                                xdata.mv_size = fp->mp_upper;
4050
 
                                xdata.mv_data = pbuf;
 
4261
                                xdata.mv_data = fp;
4051
4262
                                flags |= F_DUPDATA;
4052
4263
                                goto new_sub;
4053
4264
                        }
4100
4311
                                        /* no, just grow it */
4101
4312
                                        rdata = &xdata;
4102
4313
                                        xdata.mv_size = NODEDSZ(leaf) + offset;
4103
 
                                        xdata.mv_data = pbuf;
4104
 
                                        mp = (MDB_page *)pbuf;
 
4314
                                        xdata.mv_data = &pbuf;
 
4315
                                        mp = (MDB_page *)&pbuf;
4105
4316
                                        mp->mp_pgno = mc->mc_pg[mc->mc_top]->mp_pgno;
4106
4317
                                        flags |= F_DUPDATA;
4107
4318
                                }
4126
4337
                        goto put_sub;
4127
4338
                }
4128
4339
current:
4129
 
                /* same size, just replace it */
4130
 
                if (!F_ISSET(leaf->mn_flags, F_BIGDATA) &&
4131
 
                        NODEDSZ(leaf) == data->mv_size) {
 
4340
                /* overflow page overwrites need special handling */
 
4341
                if (F_ISSET(leaf->mn_flags, F_BIGDATA)) {
 
4342
                        MDB_page *omp;
 
4343
                        pgno_t pg;
 
4344
                        int ovpages, dpages;
 
4345
 
 
4346
                        ovpages = OVPAGES(NODEDSZ(leaf), mc->mc_txn->mt_env->me_psize);
 
4347
                        dpages = OVPAGES(data->mv_size, mc->mc_txn->mt_env->me_psize);
 
4348
                        memcpy(&pg, NODEDATA(leaf), sizeof(pg));
 
4349
                        mdb_page_get(mc->mc_txn, pg, &omp);
 
4350
                        /* Is the ov page writable and large enough? */
 
4351
                        if ((omp->mp_flags & P_DIRTY) && ovpages >= dpages) {
 
4352
                                /* yes, overwrite it. Note in this case we don't
 
4353
                                 * bother to try shrinking the node if the new data
 
4354
                                 * is smaller than the overflow threshold.
 
4355
                                 */
 
4356
                                if (F_ISSET(flags, MDB_RESERVE))
 
4357
                                        data->mv_data = METADATA(omp);
 
4358
                                else
 
4359
                                        memcpy(METADATA(omp), data->mv_data, data->mv_size);
 
4360
                                goto done;
 
4361
                        } else {
 
4362
                                /* no, free ovpages */
 
4363
                                int i;
 
4364
                                mc->mc_db->md_overflow_pages -= ovpages;
 
4365
                                for (i=0; i<ovpages; i++) {
 
4366
                                        DPRINTF("freed ov page %zu", pg);
 
4367
                                        mdb_midl_append(&mc->mc_txn->mt_free_pgs, pg);
 
4368
                                        pg++;
 
4369
                                }
 
4370
                        }
 
4371
                } else if (NODEDSZ(leaf) == data->mv_size) {
 
4372
                        /* same size, just replace it. Note that we could
 
4373
                         * also reuse this node if the new data is smaller,
 
4374
                         * but instead we opt to shrink the node in that case.
 
4375
                         */
4132
4376
                        if (F_ISSET(flags, MDB_RESERVE))
4133
4377
                                data->mv_data = NODEDATA(leaf);
4134
4378
                        else
4136
4380
                        goto done;
4137
4381
                }
4138
4382
                mdb_node_del(mc->mc_pg[mc->mc_top], mc->mc_ki[mc->mc_top], 0);
 
4383
                mc->mc_db->md_entries--;
4139
4384
        } else {
4140
4385
                DPRINTF("inserting key at index %i", mc->mc_ki[mc->mc_top]);
4141
4386
        }
4167
4412
                                        m3 = &m2->mc_xcursor->mx_cursor;
4168
4413
                                else
4169
4414
                                        m3 = m2;
4170
 
                                if (m3 == mc) continue;
 
4415
                                if (m3 == mc || m3->mc_snum < mc->mc_snum) continue;
4171
4416
                                if (m3->mc_pg[i] == mp && m3->mc_ki[i] >= mc->mc_ki[i]) {
4172
4417
                                        m3->mc_ki[i]++;
4173
4418
                                }
4184
4429
                 * DB are all zero size.
4185
4430
                 */
4186
4431
                if (do_sub) {
4187
 
                        MDB_db *db;
4188
4432
                        int xflags;
4189
4433
put_sub:
4190
4434
                        xdata.mv_size = 0;
4208
4452
                                        MDB_page *mp = mc->mc_pg[i];
4209
4453
 
4210
4454
                                        for (m2 = mc->mc_txn->mt_cursors[mc->mc_dbi]; m2; m2=m2->mc_next) {
4211
 
                                                if (m2 == mc) continue;
 
4455
                                                if (m2 == mc || m2->mc_snum < mc->mc_snum) continue;
4212
4456
                                                if (m2->mc_pg[i] == mp && m2->mc_ki[i] == mc->mc_ki[i]) {
4213
4457
                                                        mdb_xcursor_init1(m2, leaf);
4214
4458
                                                }
4218
4462
                        xflags |= (flags & MDB_APPEND);
4219
4463
                        rc = mdb_cursor_put(&mc->mc_xcursor->mx_cursor, data, &xdata, xflags);
4220
4464
                        if (flags & F_SUBDATA) {
4221
 
                                db = NODEDATA(leaf);
 
4465
                                void *db = NODEDATA(leaf);
4222
4466
                                memcpy(db, &mc->mc_xcursor->mx_db, sizeof(MDB_db));
4223
4467
                        }
4224
4468
                }
4268
4512
                        if (mc->mc_xcursor->mx_db.md_entries) {
4269
4513
                                if (leaf->mn_flags & F_SUBDATA) {
4270
4514
                                        /* update subDB info */
4271
 
                                        MDB_db *db = NODEDATA(leaf);
 
4515
                                        void *db = NODEDATA(leaf);
4272
4516
                                        memcpy(db, &mc->mc_xcursor->mx_db, sizeof(MDB_db));
4273
4517
                                } else {
4274
4518
                                        /* shrink fake page */
4342
4586
        size_t           sz;
4343
4587
 
4344
4588
        sz = LEAFSIZE(key, data);
4345
 
        if (data->mv_size >= env->me_psize / MDB_MINKEYS) {
 
4589
        if (sz >= env->me_psize / MDB_MINKEYS) {
4346
4590
                /* put on overflow page */
4347
4591
                sz -= data->mv_size - sizeof(pgno_t);
4348
4592
        }
4435
4679
                if (F_ISSET(flags, F_BIGDATA)) {
4436
4680
                        /* Data already on overflow page. */
4437
4681
                        node_size += sizeof(pgno_t);
4438
 
                } else if (data->mv_size >= mc->mc_txn->mt_env->me_psize / MDB_MINKEYS) {
 
4682
                } else if (node_size + data->mv_size >= mc->mc_txn->mt_env->me_psize / MDB_MINKEYS) {
4439
4683
                        int ovpages = OVPAGES(data->mv_size, mc->mc_txn->mt_env->me_psize);
4440
4684
                        /* Put data on overflow page. */
4441
 
                        DPRINTF("data size is %zu, put on overflow page",
4442
 
                            data->mv_size);
 
4685
                        DPRINTF("data size is %zu, node would be %zu, put data on overflow page",
 
4686
                            data->mv_size, node_size+data->mv_size);
4443
4687
                        node_size += sizeof(pgno_t);
4444
4688
                        if ((ofp = mdb_page_new(mc, P_OVERFLOW, ovpages)) == NULL)
4445
4689
                                return ENOMEM;
4642
4886
        mx->mx_cursor.mc_dbi = mc->mc_dbi+1;
4643
4887
        mx->mx_cursor.mc_dbflag = &mx->mx_dbflag;
4644
4888
        mx->mx_cursor.mc_snum = 0;
 
4889
        mx->mx_cursor.mc_top = 0;
4645
4890
        mx->mx_cursor.mc_flags = C_SUB;
4646
4891
        mx->mx_dbx.md_cmp = mc->mc_dbx->md_dcmp;
4647
4892
        mx->mx_dbx.md_dcmp = NULL;
4660
4905
        MDB_xcursor *mx = mc->mc_xcursor;
4661
4906
 
4662
4907
        if (node->mn_flags & F_SUBDATA) {
4663
 
                MDB_db *db = NODEDATA(node);
4664
 
                mx->mx_db = *db;
 
4908
                memcpy(&mx->mx_db, NODEDATA(node), sizeof(MDB_db));
4665
4909
                mx->mx_cursor.mc_snum = 0;
4666
4910
                mx->mx_cursor.mc_flags = C_SUB;
4667
4911
        } else {
4713
4957
        mc->mc_dbx = &txn->mt_dbxs[dbi];
4714
4958
        mc->mc_dbflag = &txn->mt_dbflags[dbi];
4715
4959
        mc->mc_snum = 0;
 
4960
        mc->mc_top = 0;
4716
4961
        mc->mc_flags = 0;
4717
4962
        if (txn->mt_dbs[dbi].md_flags & MDB_DUPSORT) {
4718
4963
                assert(mx != NULL);
4730
4975
        MDB_xcursor     *mx = NULL;
4731
4976
        size_t size = sizeof(MDB_cursor);
4732
4977
 
4733
 
        if (txn == NULL || ret == NULL || !dbi || dbi >= txn->mt_numdbs)
 
4978
        if (txn == NULL || ret == NULL || dbi >= txn->mt_numdbs)
 
4979
                return EINVAL;
 
4980
 
 
4981
        /* Allow read access to the freelist */
 
4982
        if (!dbi && !F_ISSET(txn->mt_flags, MDB_TXN_RDONLY))
4734
4983
                return EINVAL;
4735
4984
 
4736
4985
        if (txn->mt_dbs[dbi].md_flags & MDB_DUPSORT)
4818
5067
static int
4819
5068
mdb_update_key(MDB_page *mp, indx_t indx, MDB_val *key)
4820
5069
{
4821
 
        indx_t                   ptr, i, numkeys;
4822
 
        int                      delta;
4823
 
        size_t                   len;
4824
5070
        MDB_node                *node;
4825
5071
        char                    *base;
 
5072
        size_t                   len;
 
5073
        int                      delta, delta0;
 
5074
        indx_t                   ptr, i, numkeys;
4826
5075
        DKBUF;
4827
5076
 
4828
5077
        node = NODEPTR(mp, indx);
4829
5078
        ptr = mp->mp_ptrs[indx];
4830
 
        DPRINTF("update key %u (ofs %u) [%.*s] to [%s] on page %zu",
4831
 
            indx, ptr,
4832
 
            (int)node->mn_ksize, (char *)NODEKEY(node),
4833
 
                DKEY(key),
4834
 
            mp->mp_pgno);
4835
 
 
4836
 
        delta = key->mv_size - node->mn_ksize;
 
5079
#if MDB_DEBUG
 
5080
        {
 
5081
                MDB_val k2;
 
5082
                char kbuf2[(MAXKEYSIZE*2+1)];
 
5083
                k2.mv_data = NODEKEY(node);
 
5084
                k2.mv_size = node->mn_ksize;
 
5085
                DPRINTF("update key %u (ofs %u) [%s] to [%s] on page %zu",
 
5086
                        indx, ptr,
 
5087
                        mdb_dkey(&k2, kbuf2),
 
5088
                        DKEY(key),
 
5089
                        mp->mp_pgno);
 
5090
        }
 
5091
#endif
 
5092
 
 
5093
        delta0 = delta = key->mv_size - node->mn_ksize;
 
5094
 
 
5095
        /* Must be 2-byte aligned. If new key is
 
5096
         * shorter by 1, the shift will be skipped.
 
5097
         */
 
5098
        delta += (delta & 1);
4837
5099
        if (delta) {
4838
5100
                if (delta > 0 && SIZELEFT(mp) < delta) {
4839
5101
                        DPRINTF("OUCH! Not enough room, delta = %d", delta);
4852
5114
                mp->mp_upper -= delta;
4853
5115
 
4854
5116
                node = NODEPTR(mp, indx);
 
5117
        }
 
5118
 
 
5119
        /* But even if no shift was needed, update ksize */
 
5120
        if (delta0)
4855
5121
                node->mn_ksize = key->mv_size;
4856
 
        }
4857
5122
 
4858
 
        memcpy(NODEKEY(node), key->mv_data, key->mv_size);
 
5123
        if (key->mv_size)
 
5124
                memcpy(NODEKEY(node), key->mv_data, key->mv_size);
4859
5125
 
4860
5126
        return MDB_SUCCESS;
4861
5127
}
4868
5134
        int                      rc;
4869
5135
        MDB_node                *srcnode;
4870
5136
        MDB_val          key, data;
 
5137
        pgno_t  srcpg;
 
5138
        unsigned short flags;
 
5139
 
4871
5140
        DKBUF;
4872
5141
 
4873
5142
        /* Mark src and dst as dirty. */
4881
5150
                key.mv_data = LEAF2KEY(csrc->mc_pg[csrc->mc_top], csrc->mc_ki[csrc->mc_top], key.mv_size);
4882
5151
                data.mv_size = 0;
4883
5152
                data.mv_data = NULL;
 
5153
                srcpg = 0;
 
5154
                flags = 0;
4884
5155
        } else {
4885
5156
                srcnode = NODEPTR(csrc->mc_pg[csrc->mc_top], csrc->mc_ki[csrc->mc_top]);
 
5157
                assert(!((long)srcnode&1));
 
5158
                srcpg = NODEPGNO(srcnode);
 
5159
                flags = srcnode->mn_flags;
4886
5160
                if (csrc->mc_ki[csrc->mc_top] == 0 && IS_BRANCH(csrc->mc_pg[csrc->mc_top])) {
4887
5161
                        unsigned int snum = csrc->mc_snum;
4888
5162
                        MDB_node *s2;
4900
5174
                data.mv_size = NODEDSZ(srcnode);
4901
5175
                data.mv_data = NODEDATA(srcnode);
4902
5176
        }
 
5177
        if (IS_BRANCH(cdst->mc_pg[cdst->mc_top]) && cdst->mc_ki[cdst->mc_top] == 0) {
 
5178
                unsigned int snum = cdst->mc_snum;
 
5179
                MDB_node *s2;
 
5180
                MDB_val bkey;
 
5181
                /* must find the lowest key below dst */
 
5182
                mdb_page_search_root(cdst, NULL, 0);
 
5183
                s2 = NODEPTR(cdst->mc_pg[cdst->mc_top], 0);
 
5184
                bkey.mv_size = NODEKSZ(s2);
 
5185
                bkey.mv_data = NODEKEY(s2);
 
5186
                cdst->mc_snum = snum--;
 
5187
                cdst->mc_top = snum;
 
5188
                rc = mdb_update_key(cdst->mc_pg[cdst->mc_top], 0, &bkey);
 
5189
        }
 
5190
 
4903
5191
        DPRINTF("moving %s node %u [%s] on page %zu to node %u on page %zu",
4904
5192
            IS_LEAF(csrc->mc_pg[csrc->mc_top]) ? "leaf" : "branch",
4905
5193
            csrc->mc_ki[csrc->mc_top],
4909
5197
 
4910
5198
        /* Add the node to the destination page.
4911
5199
         */
4912
 
        rc = mdb_node_add(cdst, cdst->mc_ki[cdst->mc_top], &key, &data, NODEPGNO(srcnode),
4913
 
            srcnode->mn_flags);
 
5200
        rc = mdb_node_add(cdst, cdst->mc_ki[cdst->mc_top], &key, &data, srcpg, flags);
4914
5201
        if (rc != MDB_SUCCESS)
4915
5202
                return rc;
4916
5203
 
5033
5320
        } else {
5034
5321
                for (i = 0; i < NUMKEYS(csrc->mc_pg[csrc->mc_top]); i++, j++) {
5035
5322
                        srcnode = NODEPTR(csrc->mc_pg[csrc->mc_top], i);
 
5323
                        if (i == 0 && IS_BRANCH(csrc->mc_pg[csrc->mc_top])) {
 
5324
                                unsigned int snum = csrc->mc_snum;
 
5325
                                MDB_node *s2;
 
5326
                                /* must find the lowest key below src */
 
5327
                                mdb_page_search_root(csrc, NULL, 0);
 
5328
                                s2 = NODEPTR(csrc->mc_pg[csrc->mc_top], 0);
 
5329
                                key.mv_size = NODEKSZ(s2);
 
5330
                                key.mv_data = NODEKEY(s2);
 
5331
                                csrc->mc_snum = snum--;
 
5332
                                csrc->mc_top = snum;
 
5333
                        } else {
 
5334
                                key.mv_size = srcnode->mn_ksize;
 
5335
                                key.mv_data = NODEKEY(srcnode);
 
5336
                        }
5036
5337
 
5037
 
                        key.mv_size = srcnode->mn_ksize;
5038
 
                        key.mv_data = NODEKEY(srcnode);
5039
5338
                        data.mv_size = NODEDSZ(srcnode);
5040
5339
                        data.mv_data = NODEDATA(srcnode);
5041
5340
                        rc = mdb_node_add(cdst, j, &key, &data, NODEPGNO(srcnode), srcnode->mn_flags);
5071
5370
                        dbi--;
5072
5371
 
5073
5372
                for (m2 = csrc->mc_txn->mt_cursors[dbi]; m2; m2=m2->mc_next) {
5074
 
                        if (m2 == csrc) continue;
5075
5373
                        if (csrc->mc_flags & C_SUB)
5076
5374
                                m3 = &m2->mc_xcursor->mx_cursor;
5077
5375
                        else
5078
5376
                                m3 = m2;
 
5377
                        if (m3 == csrc) continue;
 
5378
                        if (m3->mc_snum < csrc->mc_snum) continue;
5079
5379
                        if (m3->mc_pg[csrc->mc_top] == csrc->mc_pg[csrc->mc_top]) {
5080
5380
                                m3->mc_pg[csrc->mc_top] = mp;
5081
5381
                                m3->mc_ki[csrc->mc_top] += nkeys;
5167
5467
                                                m3 = &m2->mc_xcursor->mx_cursor;
5168
5468
                                        else
5169
5469
                                                m3 = m2;
 
5470
                                        if (m3->mc_snum < mc->mc_snum) continue;
5170
5471
                                        if (m3->mc_pg[0] == mp) {
5171
5472
                                                m3->mc_snum = 0;
5172
5473
                                                m3->mc_top = 0;
5196
5497
                                                m3 = &m2->mc_xcursor->mx_cursor;
5197
5498
                                        else
5198
5499
                                                m3 = m2;
 
5500
                                        if (m3->mc_snum < mc->mc_snum) continue;
5199
5501
                                        if (m3->mc_pg[0] == mp) {
5200
5502
                                                m3->mc_pg[0] = mc->mc_pg[0];
5201
5503
                                        }
5276
5578
 
5277
5579
                memcpy(&pg, NODEDATA(leaf), sizeof(pg));
5278
5580
                ovpages = OVPAGES(NODEDSZ(leaf), mc->mc_txn->mt_env->me_psize);
 
5581
                mc->mc_db->md_overflow_pages -= ovpages;
5279
5582
                for (i=0; i<ovpages; i++) {
5280
5583
                        DPRINTF("freed ov page %zu", pg);
5281
5584
                        mdb_midl_append(&mc->mc_txn->mt_free_pgs, pg);
5348
5651
        unsigned int nflags)
5349
5652
{
5350
5653
        unsigned int flags;
5351
 
        int              rc = MDB_SUCCESS, ins_new = 0, new_root = 0;
 
5654
        int              rc = MDB_SUCCESS, ins_new = 0, new_root = 0, newpos = 1;
5352
5655
        indx_t           newindx;
5353
5656
        pgno_t           pgno = 0;
5354
5657
        unsigned int     i, j, split_indx, nkeys, pmax;
5367
5670
            IS_LEAF(mp) ? "leaf" : "branch", mp->mp_pgno,
5368
5671
            DKEY(newkey), mc->mc_ki[mc->mc_top]);
5369
5672
 
 
5673
        /* Create a right sibling. */
 
5674
        if ((rp = mdb_page_new(mc, mp->mp_flags, 1)) == NULL)
 
5675
                return ENOMEM;
 
5676
        DPRINTF("new right sibling: page %zu", rp->mp_pgno);
 
5677
 
5370
5678
        if (mc->mc_snum < 2) {
5371
5679
                if ((pp = mdb_page_new(mc, P_BRANCH, 1)) == NULL)
5372
5680
                        return ENOMEM;
5397
5705
                DPRINTF("parent branch page is %zu", mc->mc_pg[ptop]->mp_pgno);
5398
5706
        }
5399
5707
 
5400
 
        /* Create a right sibling. */
5401
 
        if ((rp = mdb_page_new(mc, mp->mp_flags, 1)) == NULL)
5402
 
                return ENOMEM;
5403
 
        DPRINTF("new right sibling: page %zu", rp->mp_pgno);
5404
 
 
5405
5708
        mdb_cursor_copy(mc, &mn);
5406
5709
        mn.mc_pg[mn.mc_top] = rp;
5407
5710
        mn.mc_ki[ptop] = mc->mc_ki[ptop]+1;
5415
5718
        }
5416
5719
 
5417
5720
        nkeys = NUMKEYS(mp);
5418
 
        split_indx = nkeys / 2 + 1;
 
5721
        split_indx = (nkeys + 1) / 2;
5419
5722
 
5420
5723
        if (IS_LEAF2(rp)) {
5421
5724
                char *split, *ins;
5461
5764
        }
5462
5765
 
5463
5766
        /* For leaf pages, check the split point based on what
5464
 
         * fits where, since otherwise add_node can fail.
 
5767
         * fits where, since otherwise mdb_node_add can fail.
 
5768
         *
 
5769
         * This check is only needed when the data items are
 
5770
         * relatively large, such that being off by one will
 
5771
         * make the difference between success or failure.
 
5772
         * When the size of the data items is much smaller than
 
5773
         * one-half of a page, this check is irrelevant.
5465
5774
         */
5466
5775
        if (IS_LEAF(mp)) {
5467
5776
                unsigned int psize, nsize;
5468
5777
                /* Maximum free space in an empty page */
5469
5778
                pmax = mc->mc_txn->mt_env->me_psize - PAGEHDRSZ;
5470
5779
                nsize = mdb_leaf_size(mc->mc_txn->mt_env, newkey, newdata);
5471
 
                if (newindx < split_indx) {
5472
 
                        psize = nsize;
5473
 
                        for (i=0; i<split_indx; i++) {
5474
 
                                node = NODEPTR(mp, i);
5475
 
                                psize += NODESIZE + NODEKSZ(node) + sizeof(indx_t);
5476
 
                                if (F_ISSET(node->mn_flags, F_BIGDATA))
5477
 
                                        psize += sizeof(pgno_t);
5478
 
                                else
5479
 
                                        psize += NODEDSZ(node);
5480
 
                                psize += psize & 1;
5481
 
                                if (psize > pmax) {
5482
 
                                        split_indx = i;
5483
 
                                        break;
 
5780
                if ((nkeys < 20) || (nsize > pmax/4)) {
 
5781
                        if (newindx <= split_indx) {
 
5782
                                psize = nsize;
 
5783
                                newpos = 0;
 
5784
                                for (i=0; i<split_indx; i++) {
 
5785
                                        node = NODEPTR(mp, i);
 
5786
                                        psize += NODESIZE + NODEKSZ(node) + sizeof(indx_t);
 
5787
                                        if (F_ISSET(node->mn_flags, F_BIGDATA))
 
5788
                                                psize += sizeof(pgno_t);
 
5789
                                        else
 
5790
                                                psize += NODEDSZ(node);
 
5791
                                        psize += psize & 1;
 
5792
                                        if (psize > pmax) {
 
5793
                                                if (i == split_indx - 1 && newindx == split_indx)
 
5794
                                                        newpos = 1;
 
5795
                                                else
 
5796
                                                        split_indx = i;
 
5797
                                                break;
 
5798
                                        }
5484
5799
                                }
5485
 
                        }
5486
 
                } else {
5487
 
                        psize = nsize;
5488
 
                        for (i=nkeys-1; i>=split_indx; i--) {
5489
 
                                node = NODEPTR(mp, i);
5490
 
                                psize += NODESIZE + NODEKSZ(node) + sizeof(indx_t);
5491
 
                                if (F_ISSET(node->mn_flags, F_BIGDATA))
5492
 
                                        psize += sizeof(pgno_t);
5493
 
                                else
5494
 
                                        psize += NODEDSZ(node);
5495
 
                                psize += psize & 1;
5496
 
                                if (psize > pmax) {
5497
 
                                        split_indx = i+1;
5498
 
                                        break;
 
5800
                        } else {
 
5801
                                psize = nsize;
 
5802
                                for (i=nkeys-1; i>=split_indx; i--) {
 
5803
                                        node = NODEPTR(mp, i);
 
5804
                                        psize += NODESIZE + NODEKSZ(node) + sizeof(indx_t);
 
5805
                                        if (F_ISSET(node->mn_flags, F_BIGDATA))
 
5806
                                                psize += sizeof(pgno_t);
 
5807
                                        else
 
5808
                                                psize += NODEDSZ(node);
 
5809
                                        psize += psize & 1;
 
5810
                                        if (psize > pmax) {
 
5811
                                                split_indx = i+1;
 
5812
                                                break;
 
5813
                                        }
5499
5814
                                }
5500
5815
                        }
5501
5816
                }
5502
5817
        }
5503
5818
 
5504
5819
        /* First find the separating key between the split pages.
 
5820
         * The case where newindx == split_indx is ambiguous; the
 
5821
         * new item could go to the new page or stay on the original
 
5822
         * page. If newpos == 1 it goes to the new page.
5505
5823
         */
5506
 
        if (newindx == split_indx) {
 
5824
        if (newindx == split_indx && newpos) {
5507
5825
                sepkey.mv_size = newkey->mv_size;
5508
5826
                sepkey.mv_data = newkey->mv_data;
5509
5827
        } else {
5541
5859
        if (nflags & MDB_APPEND) {
5542
5860
                mc->mc_pg[mc->mc_top] = rp;
5543
5861
                mc->mc_ki[mc->mc_top] = 0;
5544
 
                return mdb_node_add(mc, 0, newkey, newdata, newpgno, nflags);
 
5862
                rc = mdb_node_add(mc, 0, newkey, newdata, newpgno, nflags);
 
5863
                if (rc)
 
5864
                        return rc;
 
5865
                goto done;
5545
5866
        }
5546
5867
        if (IS_LEAF2(rp)) {
5547
5868
                goto done;
5563
5884
                if (i == split_indx) {
5564
5885
                /* Insert in right sibling. */
5565
5886
                /* Reset insert index for right sibling. */
5566
 
                        j = (i == newindx && ins_new);
5567
 
                        mc->mc_pg[mc->mc_top] = rp;
 
5887
                        if (i != newindx || (newpos ^ ins_new)) {
 
5888
                                j = 0;
 
5889
                                mc->mc_pg[mc->mc_top] = rp;
 
5890
                        }
5568
5891
                }
5569
5892
 
5570
5893
                if (i == newindx && !ins_new) {
5579
5902
 
5580
5903
                        ins_new = 1;
5581
5904
 
5582
 
                        /* Update page and index for the new key. */
 
5905
                        /* Update index for the new key. */
5583
5906
                        mc->mc_ki[mc->mc_top] = j;
5584
5907
                } else if (i == nkeys) {
5585
5908
                        break;
5604
5927
                }
5605
5928
 
5606
5929
                rc = mdb_node_add(mc, j, &rkey, rdata, pgno, flags);
 
5930
                if (rc) break;
5607
5931
        }
5608
5932
 
5609
5933
        nkeys = NUMKEYS(copy);
5615
5939
                mc->mc_txn->mt_env->me_psize - copy->mp_upper);
5616
5940
 
5617
5941
        /* reset back to original page */
5618
 
        if (newindx < split_indx) {
 
5942
        if (newindx < split_indx || (!newpos && newindx == split_indx)) {
5619
5943
                mc->mc_pg[mc->mc_top] = mp;
5620
5944
                if (nflags & MDB_RESERVE) {
5621
5945
                        node = NODEPTR(mp, mc->mc_ki[mc->mc_top]);
5626
5950
 
5627
5951
        /* return tmp page to freelist */
5628
5952
        copy->mp_next = mc->mc_txn->mt_env->me_dpages;
 
5953
        VGMEMP_FREE(mc->mc_txn->mt_env, copy);
5629
5954
        mc->mc_txn->mt_env->me_dpages = copy;
5630
5955
done:
5631
5956
        {
5645
5970
                        if (!(m3->mc_flags & C_INITIALIZED))
5646
5971
                                continue;
5647
5972
                        if (new_root) {
 
5973
                                int k;
5648
5974
                                /* root split */
5649
 
                                for (i=m3->mc_top; i>0; i--) {
5650
 
                                        m3->mc_ki[i+1] = m3->mc_ki[i];
5651
 
                                        m3->mc_pg[i+1] = m3->mc_pg[i];
 
5975
                                for (k=m3->mc_top; k>=0; k--) {
 
5976
                                        m3->mc_ki[k+1] = m3->mc_ki[k];
 
5977
                                        m3->mc_pg[k+1] = m3->mc_pg[k];
5652
5978
                                }
5653
5979
                                m3->mc_ki[0] = mc->mc_ki[0];
5654
5980
                                m3->mc_pg[0] = mc->mc_pg[0];
5961
6287
        if (!txn || !dbi || dbi >= txn->mt_numdbs)
5962
6288
                return EINVAL;
5963
6289
 
 
6290
        if (F_ISSET(txn->mt_flags, MDB_TXN_RDONLY))
 
6291
                return EACCES;
 
6292
 
5964
6293
        rc = mdb_cursor_open(txn, dbi, &mc);
5965
6294
        if (rc)
5966
6295
                return rc;