From b888bc4316f3f9c74b6768ddb1db1ec8fbac975e Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Tue, 19 Jun 2012 12:43:09 +0930 Subject: ntdb: optimize ntdb_fetch. We access the key on lookup, then access the data in the caller. It makes more sense to access both at once. We also put in a likely() for the case where the hash is not chained. Before: Adding 1000 records: 3644-3724(3675) ns (129656 bytes) Finding 1000 records: 1596-1696(1622) ns (129656 bytes) Missing 1000 records: 1409-1525(1452) ns (129656 bytes) Traversing 1000 records: 1636-1747(1668) ns (129656 bytes) Deleting 1000 records: 3138-3223(3175) ns (129656 bytes) Re-adding 1000 records: 3278-3414(3329) ns (129656 bytes) Appending 1000 records: 5396-5529(5426) ns (253312 bytes) Churning 1000 records: 9451-10095(9584) ns (253312 bytes) smbtorture results (--entries=1000) ntdb speed 183881-191112(188223) ops/sec After: Adding 1000 records: 3590-3701(3640) ns (129656 bytes) Finding 1000 records: 1539-1605(1566) ns (129656 bytes) Missing 1000 records: 1398-1440(1413) ns (129656 bytes) Traversing 1000 records: 1629-2015(1710) ns (129656 bytes) Deleting 1000 records: 3118-3236(3163) ns (129656 bytes) Re-adding 1000 records: 3235-3355(3275) ns (129656 bytes) Appending 1000 records: 5335-5444(5385) ns (253312 bytes) Churning 1000 records: 9350-9955(9494) ns (253312 bytes) smbtorture results (--entries=1000) ntdb speed 180559-199981(195106) ops/sec --- lib/ntdb/hash.c | 37 +++++++++++++++++++++++-------------- lib/ntdb/ntdb.c | 40 +++++++++++++++++++--------------------- lib/ntdb/private.h | 3 ++- lib/ntdb/test/run-04-basichash.c | 24 ++++++++++++------------ lib/ntdb/test/run-15-append.c | 2 +- lib/ntdb/test/run-64-bit-tdb.c | 2 +- lib/ntdb/traverse.c | 2 +- 7 files changed, 59 insertions(+), 51 deletions(-) (limited to 'lib/ntdb') diff --git a/lib/ntdb/hash.c b/lib/ntdb/hash.c index 69192a119b..ad1196ecde 100644 --- a/lib/ntdb/hash.c +++ b/lib/ntdb/hash.c @@ -33,7 +33,8 @@ uint32_t ntdb_hash(struct ntdb_context *ntdb, const void *ptr, size_t len) static ntdb_bool_err key_matches(struct ntdb_context *ntdb, const struct ntdb_used_record *rec, ntdb_off_t off, - const NTDB_DATA *key) + const NTDB_DATA *key, + const char **rptr) { ntdb_bool_err ret = false; const char *rkey; @@ -43,14 +44,20 @@ static ntdb_bool_err key_matches(struct ntdb_context *ntdb, return ret; } - rkey = ntdb_access_read(ntdb, off + sizeof(*rec), key->dsize, false); + rkey = ntdb_access_read(ntdb, off + sizeof(*rec), + key->dsize + rec_data_length(rec), false); if (NTDB_PTR_IS_ERR(rkey)) { return (ntdb_bool_err)NTDB_PTR_ERR(rkey); } - if (memcmp(rkey, key->dptr, key->dsize) == 0) - ret = true; - else - ntdb->stats.compare_wrong_keycmp++; + if (memcmp(rkey, key->dptr, key->dsize) == 0) { + if (rptr) { + *rptr = rkey; + } else { + ntdb_access_release(ntdb, rkey); + } + return true; + } + ntdb->stats.compare_wrong_keycmp++; ntdb_access_release(ntdb, rkey); return ret; } @@ -61,6 +68,7 @@ static ntdb_bool_err match(struct ntdb_context *ntdb, const NTDB_DATA *key, ntdb_off_t val, struct ntdb_used_record *rec, + const char **rptr, const ntdb_off_t **mapped) { ntdb_off_t off; @@ -87,7 +95,7 @@ static ntdb_bool_err match(struct ntdb_context *ntdb, return (ntdb_bool_err)ecode; } - return key_matches(ntdb, rec, off, key); + return key_matches(ntdb, rec, off, key, rptr); } static bool is_chain(ntdb_off_t val) @@ -107,10 +115,11 @@ static ntdb_off_t hbucket_off(ntdb_off_t base, ntdb_len_t idx) * If not found, the return value is 0. * If found, the return value is the offset, and *rec is the record. */ ntdb_off_t find_and_lock(struct ntdb_context *ntdb, - NTDB_DATA key, - int ltype, - struct hash_info *h, - struct ntdb_used_record *rec) + NTDB_DATA key, + int ltype, + struct hash_info *h, + struct ntdb_used_record *rec, + const char **rptr) { ntdb_off_t off, val; const ntdb_off_t *arr = NULL; @@ -140,9 +149,9 @@ ntdb_off_t find_and_lock(struct ntdb_context *ntdb, } /* Directly in hash table? */ - if (!is_chain(val)) { + if (!likely(is_chain(val))) { if (val) { - berr = match(ntdb, h->h, &key, val, rec, NULL); + berr = match(ntdb, h->h, &key, val, rec, rptr, NULL); if (berr < 0) { ecode = NTDB_OFF_TO_ERR(berr); goto fail; @@ -195,7 +204,7 @@ ntdb_off_t find_and_lock(struct ntdb_context *ntdb, found_empty = true; } } else { - berr = match(ntdb, h->h, &key, val, rec, &arr); + berr = match(ntdb, h->h, &key, val, rec, rptr, &arr); if (berr < 0) { ecode = NTDB_OFF_TO_ERR(berr); if (arr) { diff --git a/lib/ntdb/ntdb.c b/lib/ntdb/ntdb.c index 8d50ba60c1..ddbf7d6e9e 100644 --- a/lib/ntdb/ntdb.c +++ b/lib/ntdb/ntdb.c @@ -114,7 +114,7 @@ _PUBLIC_ enum NTDB_ERROR ntdb_store(struct ntdb_context *ntdb, struct ntdb_used_record rec; enum NTDB_ERROR ecode; - off = find_and_lock(ntdb, key, F_WRLCK, &h, &rec); + off = find_and_lock(ntdb, key, F_WRLCK, &h, &rec, NULL); if (NTDB_OFF_IS_ERR(off)) { return NTDB_OFF_TO_ERR(off); } @@ -176,7 +176,7 @@ _PUBLIC_ enum NTDB_ERROR ntdb_append(struct ntdb_context *ntdb, NTDB_DATA new_dbuf; enum NTDB_ERROR ecode; - off = find_and_lock(ntdb, key, F_WRLCK, &h, &rec); + off = find_and_lock(ntdb, key, F_WRLCK, &h, &rec, NULL); if (NTDB_OFF_IS_ERR(off)) { return NTDB_OFF_TO_ERR(off); } @@ -240,8 +240,9 @@ _PUBLIC_ enum NTDB_ERROR ntdb_fetch(struct ntdb_context *ntdb, NTDB_DATA key, struct ntdb_used_record rec; struct hash_info h; enum NTDB_ERROR ecode; + const char *keyp; - off = find_and_lock(ntdb, key, F_RDLCK, &h, &rec); + off = find_and_lock(ntdb, key, F_RDLCK, &h, &rec, &keyp); if (NTDB_OFF_IS_ERR(off)) { return NTDB_OFF_TO_ERR(off); } @@ -250,12 +251,14 @@ _PUBLIC_ enum NTDB_ERROR ntdb_fetch(struct ntdb_context *ntdb, NTDB_DATA key, ecode = NTDB_ERR_NOEXIST; } else { data->dsize = rec_data_length(&rec); - data->dptr = ntdb_alloc_read(ntdb, off + sizeof(rec) + key.dsize, - data->dsize); - if (NTDB_PTR_IS_ERR(data->dptr)) { - ecode = NTDB_PTR_ERR(data->dptr); - } else + data->dptr = ntdb->alloc_fn(ntdb, data->dsize, ntdb->alloc_data); + if (unlikely(!data->dptr)) { + ecode = NTDB_ERR_OOM; + } else { + memcpy(data->dptr, keyp + key.dsize, data->dsize); ecode = NTDB_SUCCESS; + } + ntdb_access_release(ntdb, keyp); } ntdb_unlock_hash(ntdb, h.h, F_RDLCK); @@ -268,7 +271,7 @@ _PUBLIC_ bool ntdb_exists(struct ntdb_context *ntdb, NTDB_DATA key) struct ntdb_used_record rec; struct hash_info h; - off = find_and_lock(ntdb, key, F_RDLCK, &h, &rec); + off = find_and_lock(ntdb, key, F_RDLCK, &h, &rec, NULL); if (NTDB_OFF_IS_ERR(off)) { return false; } @@ -284,7 +287,7 @@ _PUBLIC_ enum NTDB_ERROR ntdb_delete(struct ntdb_context *ntdb, NTDB_DATA key) struct hash_info h; enum NTDB_ERROR ecode; - off = find_and_lock(ntdb, key, F_WRLCK, &h, &rec); + off = find_and_lock(ntdb, key, F_WRLCK, &h, &rec, NULL); if (NTDB_OFF_IS_ERR(off)) { return NTDB_OFF_TO_ERR(off); } @@ -481,8 +484,9 @@ _PUBLIC_ enum NTDB_ERROR ntdb_parse_record_(struct ntdb_context *ntdb, struct ntdb_used_record rec; struct hash_info h; enum NTDB_ERROR ecode; + const char *keyp; - off = find_and_lock(ntdb, key, F_RDLCK, &h, &rec); + off = find_and_lock(ntdb, key, F_RDLCK, &h, &rec, &keyp); if (NTDB_OFF_IS_ERR(off)) { return NTDB_OFF_TO_ERR(off); } @@ -490,17 +494,11 @@ _PUBLIC_ enum NTDB_ERROR ntdb_parse_record_(struct ntdb_context *ntdb, if (!off) { ecode = NTDB_ERR_NOEXIST; } else { - const void *dptr; - dptr = ntdb_access_read(ntdb, off + sizeof(rec) + key.dsize, - rec_data_length(&rec), false); - if (NTDB_PTR_IS_ERR(dptr)) { - ecode = NTDB_PTR_ERR(dptr); - } else { - NTDB_DATA d = ntdb_mkdata(dptr, rec_data_length(&rec)); + NTDB_DATA d = ntdb_mkdata(keyp + key.dsize, + rec_data_length(&rec)); - ecode = parse(key, d, data); - ntdb_access_release(ntdb, dptr); - } + ecode = parse(key, d, data); + ntdb_access_release(ntdb, keyp); } ntdb_unlock_hash(ntdb, h.h, F_RDLCK); diff --git a/lib/ntdb/private.h b/lib/ntdb/private.h index 957d85e494..90b782d303 100644 --- a/lib/ntdb/private.h +++ b/lib/ntdb/private.h @@ -369,7 +369,8 @@ ntdb_off_t find_and_lock(struct ntdb_context *ntdb, NTDB_DATA key, int ltype, struct hash_info *h, - struct ntdb_used_record *rec); + struct ntdb_used_record *rec, + const char **rkey); enum NTDB_ERROR replace_in_hash(struct ntdb_context *ntdb, const struct hash_info *h, diff --git a/lib/ntdb/test/run-04-basichash.c b/lib/ntdb/test/run-04-basichash.c index 41b49239cb..264932b988 100644 --- a/lib/ntdb/test/run-04-basichash.c +++ b/lib/ntdb/test/run-04-basichash.c @@ -38,7 +38,7 @@ int main(int argc, char *argv[]) v = 0; /* Should not find it. */ - ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec) == 0); + ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec, NULL) == 0); /* Should have created correct hash. */ ok1(h.h == ntdb_hash(ntdb, key.dptr, key.dsize)); /* Should have located space in top table, bucket 0. */ @@ -75,7 +75,7 @@ int main(int argc, char *argv[]) ok1(ntdb_check(ntdb, NULL, NULL) == 0); /* Now, this should give a successful lookup. */ - ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec) == new_off); + ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec, NULL) == new_off); /* Should have created correct hash. */ ok1(h.h == ntdb_hash(ntdb, key.dptr, key.dsize)); /* Should have located it in top table, bucket 0. */ @@ -97,7 +97,7 @@ int main(int argc, char *argv[]) /* Test expansion. */ v = 1; - ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec) == 0); + ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec, NULL) == 0); /* Should have created correct hash. */ ok1(h.h == ntdb_hash(ntdb, key.dptr, key.dsize)); /* Should have located clash in toplevel bucket 0. */ @@ -131,7 +131,7 @@ int main(int argc, char *argv[]) /* Should be able to find both. */ v = 1; - ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec) == new_off2); + ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec, NULL) == new_off2); /* Should have created correct hash. */ ok1(h.h == ntdb_hash(ntdb, key.dptr, key.dsize)); /* Should have located space in chain. */ @@ -146,7 +146,7 @@ int main(int argc, char *argv[]) ok1(ntdb_unlock_hash(ntdb, h.h, F_WRLCK) == 0); v = 0; - ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec) == new_off); + ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec, NULL) == new_off); /* Should have created correct hash. */ ok1(h.h == ntdb_hash(ntdb, key.dptr, key.dsize)); /* Should have located space in chain. */ @@ -174,7 +174,7 @@ int main(int argc, char *argv[]) /* Should still be able to find other record. */ v = 1; - ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec) == new_off2); + ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec, NULL) == new_off2); /* Should have created correct hash. */ ok1(h.h == ntdb_hash(ntdb, key.dptr, key.dsize)); /* Should have located space in chain. */ @@ -190,7 +190,7 @@ int main(int argc, char *argv[]) /* Now should find empty space. */ v = 0; - ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec) == 0); + ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec, NULL) == 0); /* Should have created correct hash. */ ok1(h.h == ntdb_hash(ntdb, key.dptr, key.dsize)); /* Should have located space in chain, bucket 0. */ @@ -201,7 +201,7 @@ int main(int argc, char *argv[]) /* Adding another record should work. */ v = 2; - ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec) == 0); + ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec, NULL) == 0); /* Should have created correct hash. */ ok1(h.h == ntdb_hash(ntdb, key.dptr, key.dsize)); /* Should have located space in chain, bucket 0. */ @@ -229,7 +229,7 @@ int main(int argc, char *argv[]) /* Adding another record should cause expansion. */ v = 3; - ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec) == 0); + ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec, NULL) == 0); /* Should have created correct hash. */ ok1(h.h == ntdb_hash(ntdb, key.dptr, key.dsize)); /* Should not have located space in chain. */ @@ -255,7 +255,7 @@ int main(int argc, char *argv[]) ok1(ntdb_unlock_hash(ntdb, h.h, F_WRLCK) == 0); /* Retrieve it and check. */ - ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec) == new_off); + ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec, NULL) == new_off); /* Should have created correct hash. */ ok1(h.h == ntdb_hash(ntdb, key.dptr, key.dsize)); /* Should have appended to chain, bucket 2. */ @@ -272,7 +272,7 @@ int main(int argc, char *argv[]) /* YA record: relocation. */ v = 4; - ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec) == 0); + ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec, NULL) == 0); /* Should have created correct hash. */ ok1(h.h == ntdb_hash(ntdb, key.dptr, key.dsize)); /* Should not have located space in chain. */ @@ -298,7 +298,7 @@ int main(int argc, char *argv[]) ok1(ntdb_unlock_hash(ntdb, h.h, F_WRLCK) == 0); /* Retrieve it and check. */ - ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec) == new_off); + ok1(find_and_lock(ntdb, key, F_WRLCK, &h, &rec, NULL) == new_off); /* Should have created correct hash. */ ok1(h.h == ntdb_hash(ntdb, key.dptr, key.dsize)); /* Should have appended to chain, bucket 2. */ diff --git a/lib/ntdb/test/run-15-append.c b/lib/ntdb/test/run-15-append.c index 97fd53c241..a797944b53 100644 --- a/lib/ntdb/test/run-15-append.c +++ b/lib/ntdb/test/run-15-append.c @@ -12,7 +12,7 @@ static ntdb_off_t ntdb_offset(struct ntdb_context *ntdb, NTDB_DATA key) struct ntdb_used_record urec; struct hash_info h; - off = find_and_lock(ntdb, key, F_RDLCK, &h, &urec); + off = find_and_lock(ntdb, key, F_RDLCK, &h, &urec, NULL); if (NTDB_OFF_IS_ERR(off)) return 0; ntdb_unlock_hash(ntdb, h.h, F_RDLCK); diff --git a/lib/ntdb/test/run-64-bit-tdb.c b/lib/ntdb/test/run-64-bit-tdb.c index 5afdd8747c..582deb2234 100644 --- a/lib/ntdb/test/run-64-bit-tdb.c +++ b/lib/ntdb/test/run-64-bit-tdb.c @@ -67,7 +67,7 @@ int main(int argc, char *argv[]) ok1(ntdb_check(ntdb, NULL, NULL) == NTDB_SUCCESS); /* Make sure it put it at end as we expected. */ - off = find_and_lock(ntdb, k, F_RDLCK, &h, &rec); + off = find_and_lock(ntdb, k, F_RDLCK, &h, &rec, NULL); ok1(off >= ALMOST_4G); ntdb_unlock_hash(ntdb, h.h, F_RDLCK); diff --git a/lib/ntdb/traverse.c b/lib/ntdb/traverse.c index d0ce3517b0..2e6763cbdd 100644 --- a/lib/ntdb/traverse.c +++ b/lib/ntdb/traverse.c @@ -62,7 +62,7 @@ _PUBLIC_ enum NTDB_ERROR ntdb_nextkey(struct ntdb_context *ntdb, NTDB_DATA *key) struct ntdb_used_record rec; ntdb_off_t off; - off = find_and_lock(ntdb, *key, F_RDLCK, &h, &rec); + off = find_and_lock(ntdb, *key, F_RDLCK, &h, &rec, NULL); ntdb->free_fn(key->dptr, ntdb->alloc_data); if (NTDB_OFF_IS_ERR(off)) { return NTDB_OFF_TO_ERR(off); -- cgit