From: Rusty Russell Date: Sat, 18 Jul 2009 05:57:40 +0000 (+0930) Subject: Merge. X-Git-Url: https://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=3c81225fc0a4fb99d10282ebf11b7ec6ae1eabdd;hp=33480b45899ab1095bf95717d26f86244ca6d8e9 Merge. --- diff --git a/ccan/tap/tap.3 b/ccan/tap/tap.3 index 5395aef7..0abab740 100644 --- a/ccan/tap/tap.3 +++ b/ccan/tap/tap.3 @@ -16,9 +16,9 @@ their success or failure. .Ss PRINTF STRINGS In the descriptions that follow, for any function that takes as the last two parameters -.Dq Fa char * , Fa ... +.Dq Fa const char * , Fa ... it can be assumed that the -.Fa char * +.Fa const char * is a .Fn printf -like format string, and the optional arguments are values to be placed @@ -35,7 +35,7 @@ in that string. .Xc .It Xo .Ft void -.Fn plan_skip_all "char *" "..." +.Fn plan_skip_all "const char *" "..." .Xc .El .Pp @@ -74,7 +74,7 @@ the tests. .Bl -tag -width indent .It Xo .Ft unsigned int -.Fn ok "expression" "char *" "..." +.Fn ok "expression" "const char *" "..." .Xc .It Xo .Ft unsigned int @@ -82,11 +82,11 @@ the tests. .Xc .It Xo .Ft unsigned int -.Fn pass "char *" "..." +.Fn pass "const char *" "..." .Xc .It Xo .Ft unsigned int -.Fn fail "char *" "..." +.Fn fail "const char *" "..." .Xc .El .Pp @@ -161,10 +161,10 @@ These are synonyms for ok(1, ...) and ok(0, ...). .Bl -tag -width indent .It Xo .Ft void -.Fn skip "unsigned int" "char *" "..." +.Fn skip "unsigned int" "const char *" "..." .Xc .It Xo -.Fn skip_if "expression" "unsigned int" "char *" "..." +.Fn skip_if "expression" "unsigned int" "const char *" "..." .Xc .El .Pp @@ -204,7 +204,7 @@ skip_if(getuid() != 0, 1, "because test only works as root") { .Bl -tag -width indent .It Xo .Ft void -.Fn todo_start "char *" "..." +.Fn todo_start "const char *" "..." .Xc .It Xo .Ft void @@ -261,8 +261,8 @@ yet to fix, but want to put tests in your testing script .Ss DIAGNOSTIC OUTPUT .Bl -tag -width indent .It Xo -.Fr void -.Fn diag "char *" "..." +.Fr int +.Fn diag "const char *" "..." .Xc .El .Pp @@ -273,6 +273,7 @@ It ensures that the output will not be considered by the TAP test harness. adds the necessary trailing .Dq \en for you. +It returns the number of characters written. .Bd -literal -offset indent diag("Expected return code 0, got return code %d", rcode); .Ed diff --git a/ccan/tap/tap.c b/ccan/tap/tap.c index 0eaec9a5..a5156aa1 100644 --- a/ccan/tap/tap.c +++ b/ccan/tap/tap.c @@ -42,7 +42,7 @@ static unsigned int test_count = 0; /* Number of tests that have been run */ static unsigned int e_tests = 0; /* Expected number of tests to run */ static unsigned int failures = 0; /* Number of tests that failed */ static char *todo_msg = NULL; -static char *todo_msg_fixed = "libtap malloc issue"; +static const char *todo_msg_fixed = "libtap malloc issue"; static int todo = 0; static int test_died = 0; static int test_pid; @@ -68,7 +68,7 @@ _expected_tests(unsigned int tests) } static void -diagv(char *fmt, va_list ap) +diagv(const char *fmt, va_list ap) { fputs("# ", stdout); vfprintf(stdout, fmt, ap); @@ -76,7 +76,7 @@ diagv(char *fmt, va_list ap) } static void -_diag(char *fmt, ...) +_diag(const char *fmt, ...) { va_list ap; va_start(ap, fmt); @@ -92,8 +92,8 @@ _diag(char *fmt, ...) * test_comment -- a comment to print afterwards, may be NULL */ unsigned int -_gen_result(int ok, const char *func, char *file, unsigned int line, - char *test_name, ...) +_gen_result(int ok, const char *func, const char *file, unsigned int line, + const char *test_name, ...) { va_list ap; char *local_test_name = NULL; @@ -293,7 +293,7 @@ plan_no_plan(void) * Note that the plan is to skip all tests */ void -plan_skip_all(char *reason) +plan_skip_all(const char *reason) { LOCK; @@ -345,7 +345,7 @@ plan_tests(unsigned int tests) } void -diag(char *fmt, ...) +diag(const char *fmt, ...) { va_list ap; @@ -359,7 +359,7 @@ diag(char *fmt, ...) } void -skip(unsigned int n, char *fmt, ...) +skip(unsigned int n, const char *fmt, ...) { va_list ap; char *skip_msg; @@ -384,7 +384,7 @@ skip(unsigned int n, char *fmt, ...) } void -todo_start(char *fmt, ...) +todo_start(const char *fmt, ...) { va_list ap; diff --git a/ccan/tap/tap.h b/ccan/tap/tap.h index f854d3e3..1dad6365 100644 --- a/ccan/tap/tap.h +++ b/ccan/tap/tap.h @@ -124,8 +124,8 @@ void plan_tests(unsigned int tests); #endif #endif -unsigned int _gen_result(int, const char *, char *, unsigned int, char *, ...) - PRINTF_ATTRIBUTE(5, 6); +unsigned int _gen_result(int, const char *, const char *, unsigned int, + const char *, ...) PRINTF_ATTRIBUTE(5, 6); /** * diag - print a diagnostic message (use instead of printf/fprintf) @@ -137,7 +137,7 @@ unsigned int _gen_result(int, const char *, char *, unsigned int, char *, ...) * Example: * diag("Now running complex tests"); */ -void diag(char *fmt, ...) PRINTF_ATTRIBUTE(1, 2); +void diag(const char *fmt, ...) PRINTF_ATTRIBUTE(1, 2); /** * skip - print a diagnostic message (use instead of printf/fprintf) @@ -160,7 +160,7 @@ void diag(char *fmt, ...) PRINTF_ATTRIBUTE(1, 2); * skip(1, "Don't have SOME_FEATURE"); * #endif */ -void skip(unsigned int n, char *fmt, ...) PRINTF_ATTRIBUTE(2, 3); +void skip(unsigned int n, const char *fmt, ...) PRINTF_ATTRIBUTE(2, 3); /** * todo_start - mark tests that you expect to fail. @@ -185,7 +185,7 @@ void skip(unsigned int n, char *fmt, ...) PRINTF_ATTRIBUTE(2, 3); * ok(dwim(), "Did what the user wanted"); * todo_end(); */ -void todo_start(char *fmt, ...) PRINTF_ATTRIBUTE(1, 2); +void todo_start(const char *fmt, ...) PRINTF_ATTRIBUTE(1, 2); /** * todo_end - end of tests you expect to fail. @@ -241,6 +241,6 @@ void plan_no_plan(void); * } * plan_tests(13); */ -void plan_skip_all(char *reason); +void plan_skip_all(const char *reason); #endif /* C99 or gcc */ diff --git a/ccan/tdb/io.c b/ccan/tdb/io.c index c25f1cb4..d8140fea 100644 --- a/ccan/tdb/io.c +++ b/ccan/tdb/io.c @@ -383,11 +383,7 @@ unsigned char *tdb_alloc_read(struct tdb_context *tdb, tdb_off_t offset, tdb_len unsigned char *buf; /* some systems don't like zero length malloc */ - if (len == 0) { - len = 1; - } - - if (!(buf = (unsigned char *)malloc(len))) { + if (!(buf = (unsigned char *)malloc(len ? len : 1))) { /* Ensure ecode is set for log fn. */ tdb->ecode = TDB_ERR_OOM; TDB_LOG((tdb, TDB_DEBUG_ERROR,"tdb_alloc_read malloc failed len=%d (%s)\n", diff --git a/ccan/tdb/lock.c b/ccan/tdb/lock.c index f156c0fa..bcd560d7 100644 --- a/ccan/tdb/lock.c +++ b/ccan/tdb/lock.c @@ -301,7 +301,11 @@ int tdb_unlock(struct tdb_context *tdb, int list, int ltype) */ int tdb_transaction_lock(struct tdb_context *tdb, int ltype) { - if (tdb->have_transaction_lock || tdb->global_lock.count) { + if (tdb->global_lock.count) { + return 0; + } + if (tdb->have_transaction_lock) { + tdb->have_transaction_lock++; return 0; } if (tdb->methods->tdb_brlock(tdb, TRANSACTION_LOCK, ltype, @@ -310,7 +314,7 @@ int tdb_transaction_lock(struct tdb_context *tdb, int ltype) tdb->ecode = TDB_ERR_LOCK; return -1; } - tdb->have_transaction_lock = 1; + tdb->have_transaction_lock++; return 0; } @@ -319,15 +323,13 @@ int tdb_transaction_lock(struct tdb_context *tdb, int ltype) */ int tdb_transaction_unlock(struct tdb_context *tdb) { - int ret; - if (!tdb->have_transaction_lock) { + if (tdb->global_lock.count) { return 0; } - ret = tdb->methods->tdb_brlock(tdb, TRANSACTION_LOCK, F_UNLCK, F_SETLKW, 0, 1); - if (ret == 0) { - tdb->have_transaction_lock = 0; + if (--tdb->have_transaction_lock) { + return 0; } - return ret; + return tdb->methods->tdb_brlock(tdb, TRANSACTION_LOCK, F_UNLCK, F_SETLKW, 0, 1); } @@ -413,48 +415,58 @@ static int _tdb_unlockall(struct tdb_context *tdb, int ltype) /* lock entire database with write lock */ int tdb_lockall(struct tdb_context *tdb) { + tdb_trace(tdb, "tdb_lockall"); return _tdb_lockall(tdb, F_WRLCK, F_SETLKW); } /* lock entire database with write lock - mark only */ int tdb_lockall_mark(struct tdb_context *tdb) { + tdb_trace(tdb, "tdb_lockall_mark"); return _tdb_lockall(tdb, F_WRLCK | TDB_MARK_LOCK, F_SETLKW); } /* unlock entire database with write lock - unmark only */ int tdb_lockall_unmark(struct tdb_context *tdb) { + tdb_trace(tdb, "tdb_lockall_unmark"); return _tdb_unlockall(tdb, F_WRLCK | TDB_MARK_LOCK); } /* lock entire database with write lock - nonblocking varient */ int tdb_lockall_nonblock(struct tdb_context *tdb) { - return _tdb_lockall(tdb, F_WRLCK, F_SETLK); + int ret = _tdb_lockall(tdb, F_WRLCK, F_SETLK); + tdb_trace_ret(tdb, "tdb_lockall_nonblock", ret); + return ret; } /* unlock entire database with write lock */ int tdb_unlockall(struct tdb_context *tdb) { + tdb_trace(tdb, "tdb_unlockall"); return _tdb_unlockall(tdb, F_WRLCK); } /* lock entire database with read lock */ int tdb_lockall_read(struct tdb_context *tdb) { + tdb_trace(tdb, "tdb_lockall_read"); return _tdb_lockall(tdb, F_RDLCK, F_SETLKW); } /* lock entire database with read lock - nonblock varient */ int tdb_lockall_read_nonblock(struct tdb_context *tdb) { - return _tdb_lockall(tdb, F_RDLCK, F_SETLK); + int ret = _tdb_lockall(tdb, F_RDLCK, F_SETLK); + tdb_trace_ret(tdb, "tdb_lockall_read_nonblock", ret); + return ret; } /* unlock entire database with read lock */ int tdb_unlockall_read(struct tdb_context *tdb) { + tdb_trace(tdb, "tdb_unlockall_read"); return _tdb_unlockall(tdb, F_RDLCK); } @@ -462,7 +474,9 @@ int tdb_unlockall_read(struct tdb_context *tdb) contention - it cannot guarantee how many records will be locked */ int tdb_chainlock(struct tdb_context *tdb, TDB_DATA key) { - return tdb_lock(tdb, BUCKET(tdb->hash_fn(&key)), F_WRLCK); + int ret = tdb_lock(tdb, BUCKET(tdb->hash_fn(&key)), F_WRLCK); + tdb_trace_1rec(tdb, "tdb_chainlock", key); + return ret; } /* lock/unlock one hash chain, non-blocking. This is meant to be used @@ -470,38 +484,46 @@ int tdb_chainlock(struct tdb_context *tdb, TDB_DATA key) locked */ int tdb_chainlock_nonblock(struct tdb_context *tdb, TDB_DATA key) { - return tdb_lock_nonblock(tdb, BUCKET(tdb->hash_fn(&key)), F_WRLCK); + int ret = tdb_lock_nonblock(tdb, BUCKET(tdb->hash_fn(&key)), F_WRLCK); + tdb_trace_1rec_ret(tdb, "tdb_chainlock_nonblock", key, ret); + return ret; } /* mark a chain as locked without actually locking it. Warning! use with great caution! */ int tdb_chainlock_mark(struct tdb_context *tdb, TDB_DATA key) { - return tdb_lock(tdb, BUCKET(tdb->hash_fn(&key)), F_WRLCK | TDB_MARK_LOCK); + int ret = tdb_lock(tdb, BUCKET(tdb->hash_fn(&key)), F_WRLCK | TDB_MARK_LOCK); + tdb_trace_1rec(tdb, "tdb_chainlock_mark", key); + return ret; } /* unmark a chain as locked without actually locking it. Warning! use with great caution! */ int tdb_chainlock_unmark(struct tdb_context *tdb, TDB_DATA key) { + tdb_trace_1rec(tdb, "tdb_chainlock_unmark", key); return tdb_unlock(tdb, BUCKET(tdb->hash_fn(&key)), F_WRLCK | TDB_MARK_LOCK); } int tdb_chainunlock(struct tdb_context *tdb, TDB_DATA key) { + tdb_trace_1rec(tdb, "tdb_chainunlock", key); return tdb_unlock(tdb, BUCKET(tdb->hash_fn(&key)), F_WRLCK); } int tdb_chainlock_read(struct tdb_context *tdb, TDB_DATA key) { - return tdb_lock(tdb, BUCKET(tdb->hash_fn(&key)), F_RDLCK); + int ret; + ret = tdb_lock(tdb, BUCKET(tdb->hash_fn(&key)), F_RDLCK); + tdb_trace_1rec(tdb, "tdb_chainlock_read", key); + return ret; } int tdb_chainunlock_read(struct tdb_context *tdb, TDB_DATA key) { + tdb_trace_1rec(tdb, "tdb_chainunlock_read", key); return tdb_unlock(tdb, BUCKET(tdb->hash_fn(&key)), F_RDLCK); } - - /* record lock stops delete underneath */ int tdb_lock_record(struct tdb_context *tdb, tdb_off_t off) { diff --git a/ccan/tdb/open.c b/ccan/tdb/open.c index 8cd25cc5..69885284 100644 --- a/ccan/tdb/open.c +++ b/ccan/tdb/open.c @@ -206,6 +206,10 @@ struct tdb_context *tdb_open_ex(const char *name, int hash_size, int tdb_flags, TDB_LOG((tdb, TDB_DEBUG_ERROR, "tdb_open_ex: tdb_new_database failed!")); goto fail; } +#ifdef TDB_TRACE + /* All tracing will fail. That's ok. */ + tdb->tracefd = -1; +#endif goto internal; } @@ -314,6 +318,20 @@ struct tdb_context *tdb_open_ex(const char *name, int hash_size, int tdb_flags, goto fail; } +#ifdef TDB_TRACE + { + char tracefile[strlen(name) + 32]; + + sprintf(tracefile, "%s.trace.%u", name, getpid()); + tdb->tracefd = open(tracefile, O_WRONLY|O_CREAT|O_EXCL, 0600); + if (tdb->tracefd < 0) + goto fail; + tdb_enable_seqnum(tdb); + tdb_trace_open(tdb, "tdb_open", hash_size, tdb_flags, + open_flags); + } +#endif + internal: /* Internal (memory-only) databases skip all the code above to * do with disk files, and resume here by releasing their @@ -329,6 +347,8 @@ struct tdb_context *tdb_open_ex(const char *name, int hash_size, int tdb_flags, if (!tdb) return NULL; + + close(tdb->tracefd); if (tdb->map_ptr) { if (tdb->flags & TDB_INTERNAL) @@ -365,8 +385,9 @@ int tdb_close(struct tdb_context *tdb) struct tdb_context **i; int ret = 0; + tdb_trace(tdb, "tdb_close"); if (tdb->transaction) { - tdb_transaction_cancel(tdb); + tdb_transaction_cancel_internal(tdb); } if (tdb->map_ptr) { @@ -388,6 +409,7 @@ int tdb_close(struct tdb_context *tdb) } } + close(tdb->tracefd); memset(tdb, 0, sizeof(*tdb)); SAFE_FREE(tdb); diff --git a/ccan/tdb/tdb.c b/ccan/tdb/tdb.c index 767452c9..3acf05b9 100644 --- a/ccan/tdb/tdb.c +++ b/ccan/tdb/tdb.c @@ -153,7 +153,7 @@ static int tdb_update_hash(struct tdb_context *tdb, TDB_DATA key, uint32_t hash, * then the TDB_DATA will have zero length but * a non-zero pointer */ -TDB_DATA tdb_fetch(struct tdb_context *tdb, TDB_DATA key) +static TDB_DATA do_tdb_fetch(struct tdb_context *tdb, TDB_DATA key) { tdb_off_t rec_ptr; struct list_struct rec; @@ -162,9 +162,9 @@ TDB_DATA tdb_fetch(struct tdb_context *tdb, TDB_DATA key) /* find which hash bucket it is in */ hash = tdb->hash_fn(&key); - if (!(rec_ptr = tdb_find_lock_hash(tdb,key,hash,F_RDLCK,&rec))) + if (!(rec_ptr = tdb_find_lock_hash(tdb,key,hash,F_RDLCK,&rec))) { return tdb_null; - + } ret.dptr = tdb_alloc_read(tdb, rec_ptr + sizeof(rec) + rec.key_len, rec.data_len); ret.dsize = rec.data_len; @@ -172,6 +172,14 @@ TDB_DATA tdb_fetch(struct tdb_context *tdb, TDB_DATA key) return ret; } +TDB_DATA tdb_fetch(struct tdb_context *tdb, TDB_DATA key) +{ + TDB_DATA ret = do_tdb_fetch(tdb, key); + + tdb_trace_1rec_retrec(tdb, "tdb_fetch", key, ret); + return ret; +} + /* * Find an entry in the database and hand the record's data to a parsing * function. The parsing function is executed under the chain read lock, so it @@ -202,8 +210,11 @@ int tdb_parse_record(struct tdb_context *tdb, TDB_DATA key, hash = tdb->hash_fn(&key); if (!(rec_ptr = tdb_find_lock_hash(tdb,key,hash,F_RDLCK,&rec))) { + tdb_trace_1rec_ret(tdb, "tdb_parse_record", key, + -TDB_ERR_NOEXIST); return TDB_ERRCODE(TDB_ERR_NOEXIST, 0); } + tdb_trace_1rec_ret(tdb, "tdb_parse_record", key, 0); ret = tdb_parse_data(tdb, key, rec_ptr + sizeof(rec) + rec.key_len, rec.data_len, parser, private_data); @@ -232,7 +243,11 @@ static int tdb_exists_hash(struct tdb_context *tdb, TDB_DATA key, uint32_t hash) int tdb_exists(struct tdb_context *tdb, TDB_DATA key) { uint32_t hash = tdb->hash_fn(&key); - return tdb_exists_hash(tdb, key, hash); + int ret; + + ret = tdb_exists_hash(tdb, key, hash); + tdb_trace_1rec_ret(tdb, "tdb_exists", key, ret); + return ret; } /* actually delete an entry in the database given the offset */ @@ -387,7 +402,11 @@ static int tdb_delete_hash(struct tdb_context *tdb, TDB_DATA key, uint32_t hash) int tdb_delete(struct tdb_context *tdb, TDB_DATA key) { uint32_t hash = tdb->hash_fn(&key); - return tdb_delete_hash(tdb, key, hash); + int ret; + + ret = tdb_delete_hash(tdb, key, hash); + tdb_trace_1rec_ret(tdb, "tdb_delete", key, ret); + return ret; } /* @@ -419,29 +438,14 @@ static tdb_off_t tdb_find_dead(struct tdb_context *tdb, uint32_t hash, return 0; } -/* store an element in the database, replacing any existing element - with the same key - - return 0 on success, -1 on failure -*/ -int tdb_store(struct tdb_context *tdb, TDB_DATA key, TDB_DATA dbuf, int flag) +static int _tdb_store(struct tdb_context *tdb, TDB_DATA key, TDB_DATA dbuf, + int flag, uint32_t hash) { struct list_struct rec; - uint32_t hash; tdb_off_t rec_ptr; char *p = NULL; int ret = -1; - if (tdb->read_only || tdb->traverse_read) { - tdb->ecode = TDB_ERR_RDONLY; - return -1; - } - - /* find which hash bucket it is in */ - hash = tdb->hash_fn(&key); - if (tdb_lock(tdb, BUCKET(hash), F_WRLCK) == -1) - return -1; - /* check for it existing, on insert. */ if (flag == TDB_INSERT) { if (tdb_exists_hash(tdb, key, hash)) { @@ -557,6 +561,33 @@ int tdb_store(struct tdb_context *tdb, TDB_DATA key, TDB_DATA dbuf, int flag) } SAFE_FREE(p); + return ret; +} + +/* store an element in the database, replacing any existing element + with the same key + + return 0 on success, -1 on failure +*/ +int tdb_store(struct tdb_context *tdb, TDB_DATA key, TDB_DATA dbuf, int flag) +{ + uint32_t hash; + int ret; + + if (tdb->read_only || tdb->traverse_read) { + tdb->ecode = TDB_ERR_RDONLY; + tdb_trace_2rec_flag_ret(tdb, "tdb_store", key, dbuf, flag, + -TDB_ERR_RDONLY); + return -1; + } + + /* find which hash bucket it is in */ + hash = tdb->hash_fn(&key); + if (tdb_lock(tdb, BUCKET(hash), F_WRLCK) == -1) + return -1; + + ret = _tdb_store(tdb, key, dbuf, flag, hash); + tdb_trace_2rec_flag_ret(tdb, "tdb_store", key, dbuf, flag, ret); tdb_unlock(tdb, BUCKET(hash), F_WRLCK); return ret; } @@ -574,13 +605,18 @@ int tdb_append(struct tdb_context *tdb, TDB_DATA key, TDB_DATA new_dbuf) if (tdb_lock(tdb, BUCKET(hash), F_WRLCK) == -1) return -1; - dbuf = tdb_fetch(tdb, key); + dbuf = do_tdb_fetch(tdb, key); if (dbuf.dptr == NULL) { dbuf.dptr = (unsigned char *)malloc(new_dbuf.dsize); } else { - unsigned char *new_dptr = (unsigned char *)realloc(dbuf.dptr, - dbuf.dsize + new_dbuf.dsize); + unsigned int new_len = dbuf.dsize + new_dbuf.dsize; + unsigned char *new_dptr; + + /* realloc '0' is special: don't do that. */ + if (new_len == 0) + new_len = 1; + new_dptr = (unsigned char *)realloc(dbuf.dptr, new_len); if (new_dptr == NULL) { free(dbuf.dptr); } @@ -595,7 +631,8 @@ int tdb_append(struct tdb_context *tdb, TDB_DATA key, TDB_DATA new_dbuf) memcpy(dbuf.dptr + dbuf.dsize, new_dbuf.dptr, new_dbuf.dsize); dbuf.dsize += new_dbuf.dsize; - ret = tdb_store(tdb, key, dbuf, 0); + ret = _tdb_store(tdb, key, dbuf, 0, hash); + tdb_trace_2rec_retrec(tdb, "tdb_append", key, new_dbuf, dbuf); failed: tdb_unlock(tdb, BUCKET(hash), F_WRLCK); @@ -648,6 +685,7 @@ int tdb_get_seqnum(struct tdb_context *tdb) tdb_off_t seqnum=0; tdb_ofs_read(tdb, TDB_SEQNUM_OFS, &seqnum); + tdb_trace_ret(tdb, "tdb_get_seqnum", seqnum); return seqnum; } @@ -729,6 +767,8 @@ int tdb_wipe_all(struct tdb_context *tdb) return -1; } + tdb_trace(tdb, "tdb_wipe_all"); + /* see if the tdb has a recovery area, and remember its size if so. We don't want to lose this as otherwise each tdb_wipe_all() in a transaction will increase the size of @@ -800,3 +840,143 @@ failed: tdb_unlockall(tdb); return -1; } + +#ifdef TDB_TRACE +static void tdb_trace_write(struct tdb_context *tdb, const char *str) +{ + if (write(tdb->tracefd, str, strlen(str)) != strlen(str)) { + close(tdb->tracefd); + tdb->tracefd = -1; + } +} + +static void tdb_trace_start(struct tdb_context *tdb) +{ + tdb_off_t seqnum=0; + char msg[sizeof(tdb_off_t) * 4]; + + tdb_ofs_read(tdb, TDB_SEQNUM_OFS, &seqnum); + sprintf(msg, "%u ", seqnum); + tdb_trace_write(tdb, msg); +} + +static void tdb_trace_end(struct tdb_context *tdb) +{ + tdb_trace_write(tdb, "\n"); +} + +static void tdb_trace_end_ret(struct tdb_context *tdb, int ret) +{ + char msg[sizeof(ret) * 4]; + sprintf(msg, " = %i\n", ret); + tdb_trace_write(tdb, msg); +} + +static void tdb_trace_record(struct tdb_context *tdb, TDB_DATA rec) +{ + char msg[20]; + unsigned int i; + + /* We differentiate zero-length records from non-existent ones. */ + if (rec.dptr == NULL) { + tdb_trace_write(tdb, " NULL"); + return; + } + sprintf(msg, " %zu:", rec.dsize); + tdb_trace_write(tdb, msg); + for (i = 0; i < rec.dsize; i++) { + sprintf(msg, "%02x", rec.dptr[i]); + tdb_trace_write(tdb, msg); + } +} + +void tdb_trace(struct tdb_context *tdb, const char *op) +{ + tdb_trace_start(tdb); + tdb_trace_write(tdb, op); + tdb_trace_end(tdb); +} + +void tdb_trace_open(struct tdb_context *tdb, const char *op, + unsigned hash_size, unsigned tdb_flags, unsigned open_flags) +{ + char msg[128]; + + sprintf(msg, "%s %u %#x %#x", op, hash_size, tdb_flags, open_flags); + tdb_trace_start(tdb); + tdb_trace_write(tdb, msg); + tdb_trace_end(tdb); +} + +void tdb_trace_ret(struct tdb_context *tdb, const char *op, int ret) +{ + tdb_trace_start(tdb); + tdb_trace_write(tdb, op); + tdb_trace_end_ret(tdb, ret); +} + +void tdb_trace_retrec(struct tdb_context *tdb, const char *op, TDB_DATA ret) +{ + tdb_trace_start(tdb); + tdb_trace_write(tdb, op); + tdb_trace_write(tdb, " ="); + tdb_trace_record(tdb, ret); + tdb_trace_end(tdb); +} + +void tdb_trace_1rec(struct tdb_context *tdb, const char *op, + TDB_DATA rec) +{ + tdb_trace_start(tdb); + tdb_trace_write(tdb, op); + tdb_trace_record(tdb, rec); + tdb_trace_end(tdb); +} + +void tdb_trace_1rec_ret(struct tdb_context *tdb, const char *op, + TDB_DATA rec, int ret) +{ + tdb_trace_start(tdb); + tdb_trace_write(tdb, op); + tdb_trace_record(tdb, rec); + tdb_trace_end_ret(tdb, ret); +} + +void tdb_trace_1rec_retrec(struct tdb_context *tdb, const char *op, + TDB_DATA rec, TDB_DATA ret) +{ + tdb_trace_start(tdb); + tdb_trace_write(tdb, op); + tdb_trace_record(tdb, rec); + tdb_trace_write(tdb, " ="); + tdb_trace_record(tdb, ret); + tdb_trace_end(tdb); +} + +void tdb_trace_2rec_flag_ret(struct tdb_context *tdb, const char *op, + TDB_DATA rec1, TDB_DATA rec2, unsigned flag, + int ret) +{ + char msg[sizeof(ret) * 4]; + + sprintf(msg, " %#x", flag); + tdb_trace_start(tdb); + tdb_trace_write(tdb, op); + tdb_trace_record(tdb, rec1); + tdb_trace_record(tdb, rec2); + tdb_trace_write(tdb, msg); + tdb_trace_end_ret(tdb, ret); +} + +void tdb_trace_2rec_retrec(struct tdb_context *tdb, const char *op, + TDB_DATA rec1, TDB_DATA rec2, TDB_DATA ret) +{ + tdb_trace_start(tdb); + tdb_trace_write(tdb, op); + tdb_trace_record(tdb, rec1); + tdb_trace_record(tdb, rec2); + tdb_trace_write(tdb, " ="); + tdb_trace_record(tdb, ret); + tdb_trace_end(tdb); +} +#endif diff --git a/ccan/tdb/tdb_private.h b/ccan/tdb/tdb_private.h index c460af4e..48364728 100644 --- a/ccan/tdb/tdb_private.h +++ b/ccan/tdb/tdb_private.h @@ -49,6 +49,8 @@ #endif #include "tdb.h" +/* #define TDB_TRACE 1 */ + #if HAVE_GETPAGESIZE #define getpagesize() 0x2000 #endif @@ -86,6 +88,35 @@ typedef uint32_t tdb_off_t; * argument. */ #define TDB_LOG(x) tdb->log.log_fn x +#ifdef TDB_TRACE +void tdb_trace(struct tdb_context *tdb, const char *op); +void tdb_trace_open(struct tdb_context *tdb, const char *op, + unsigned hash_size, unsigned tdb_flags, unsigned open_flags); +void tdb_trace_ret(struct tdb_context *tdb, const char *op, int ret); +void tdb_trace_retrec(struct tdb_context *tdb, const char *op, TDB_DATA ret); +void tdb_trace_1rec(struct tdb_context *tdb, const char *op, + TDB_DATA rec); +void tdb_trace_1rec_ret(struct tdb_context *tdb, const char *op, + TDB_DATA rec, int ret); +void tdb_trace_1rec_retrec(struct tdb_context *tdb, const char *op, + TDB_DATA rec, TDB_DATA ret); +void tdb_trace_2rec_flag_ret(struct tdb_context *tdb, const char *op, + TDB_DATA rec1, TDB_DATA rec2, unsigned flag, + int ret); +void tdb_trace_2rec_retrec(struct tdb_context *tdb, const char *op, + TDB_DATA rec1, TDB_DATA rec2, TDB_DATA ret); +#else +#define tdb_trace(tdb, op) +#define tdb_trace_open(tdb, op, hash_size, tdb_flags, open_flags) +#define tdb_trace_ret(tdb, op, ret) +#define tdb_trace_retrec(tdb, op, ret) +#define tdb_trace_1rec(tdb, op, rec) +#define tdb_trace_1rec_ret(tdb, op, rec, ret) +#define tdb_trace_1rec_retrec(tdb, op, rec, ret) +#define tdb_trace_2rec_flag_ret(tdb, op, rec1, rec2, flag, ret) +#define tdb_trace_2rec_retrec(tdb, op, rec1, rec2, ret) +#endif /* !TDB_TRACE */ + /* lock offsets */ #define GLOBAL_LOCK 0 #define ACTIVE_LOCK 4 @@ -184,7 +215,8 @@ struct tdb_context { struct tdb_transaction *transaction; int page_size; int max_dead_records; - bool have_transaction_lock; + int have_transaction_lock; + int tracefd; volatile sig_atomic_t *interrupt_sig_ptr; }; @@ -212,6 +244,7 @@ int tdb_ofs_read(struct tdb_context *tdb, tdb_off_t offset, tdb_off_t *d); int tdb_ofs_write(struct tdb_context *tdb, tdb_off_t offset, tdb_off_t *d); int tdb_lock_record(struct tdb_context *tdb, tdb_off_t off); int tdb_unlock_record(struct tdb_context *tdb, tdb_off_t off); +int tdb_transaction_cancel_internal(struct tdb_context *tdb); int tdb_rec_read(struct tdb_context *tdb, tdb_off_t offset, struct list_struct *rec); int tdb_rec_write(struct tdb_context *tdb, tdb_off_t offset, struct list_struct *rec); int tdb_do_delete(struct tdb_context *tdb, tdb_off_t rec_ptr, struct list_struct *rec); diff --git a/ccan/tdb/test/run-nested-traverse.c b/ccan/tdb/test/run-nested-traverse.c new file mode 100644 index 00000000..f4a36b62 --- /dev/null +++ b/ccan/tdb/test/run-nested-traverse.c @@ -0,0 +1,71 @@ +#define _XOPEN_SOURCE 500 +#include "tdb/tdb.h" +#include "tdb/io.c" +#include "tdb/tdb.c" +#include "tdb/lock.c" +#include "tdb/freelist.c" +#include "tdb/traverse.c" +#include "tdb/transaction.c" +#include "tdb/error.c" +#include "tdb/open.c" +#include "tap/tap.h" +#include +#include +#include + +static bool correct_key(TDB_DATA key) +{ + return key.dsize == strlen("hi") + && memcmp(key.dptr, "hi", key.dsize) == 0; +} + +static bool correct_data(TDB_DATA data) +{ + return data.dsize == strlen("world") + && memcmp(data.dptr, "world", data.dsize) == 0; +} + +static int traverse2(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, + void *p) +{ + ok1(correct_key(key)); + ok1(correct_data(data)); + return 0; +} + +static int traverse1(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, + void *p) +{ + ok1(correct_key(key)); + ok1(correct_data(data)); + ok1(tdb->have_transaction_lock); + tdb_traverse(tdb, traverse2, NULL); + + /* That should *not* release the transaction lock! */ + ok1(tdb->have_transaction_lock); + return 0; +} + +int main(int argc, char *argv[]) +{ + struct tdb_context *tdb; + TDB_DATA key, data; + + plan_tests(14); + tdb = tdb_open("/tmp/test.tdb", 1024, TDB_CLEAR_IF_FIRST, + O_CREAT|O_TRUNC|O_RDWR, 0600); + ok1(tdb); + + /* Tickle bug on appending zero length buffer to zero length buffer. */ + key.dsize = strlen("hi"); + key.dptr = (void *)"hi"; + data.dptr = (void *)"world"; + data.dsize = strlen("world"); + + ok1(tdb_store(tdb, key, data, TDB_INSERT) == 0); + tdb_traverse(tdb, traverse1, NULL); + tdb_traverse_read(tdb, traverse1, NULL); + tdb_close(tdb); + + return exit_status(); +} diff --git a/ccan/tdb/test/run-traverse-in-transaction.c b/ccan/tdb/test/run-traverse-in-transaction.c new file mode 100644 index 00000000..b184474f --- /dev/null +++ b/ccan/tdb/test/run-traverse-in-transaction.c @@ -0,0 +1,70 @@ +#define _XOPEN_SOURCE 500 +#include "tdb/tdb.h" +#include "tdb/io.c" +#include "tdb/tdb.c" +#include "tdb/lock.c" +#include "tdb/freelist.c" +#include "tdb/traverse.c" +#include "tdb/transaction.c" +#include "tdb/error.c" +#include "tdb/open.c" +#include "tap/tap.h" +#include +#include +#include + +static bool correct_key(TDB_DATA key) +{ + return key.dsize == strlen("hi") + && memcmp(key.dptr, "hi", key.dsize) == 0; +} + +static bool correct_data(TDB_DATA data) +{ + return data.dsize == strlen("world") + && memcmp(data.dptr, "world", data.dsize) == 0; +} + +static int traverse(struct tdb_context *tdb, TDB_DATA key, TDB_DATA data, + void *p) +{ + ok1(correct_key(key)); + ok1(correct_data(data)); + return 0; +} + +int main(int argc, char *argv[]) +{ + struct tdb_context *tdb; + TDB_DATA key, data; + + plan_tests(12); + tdb = tdb_open("/tmp/test.tdb", 1024, TDB_CLEAR_IF_FIRST, + O_CREAT|O_TRUNC|O_RDWR, 0600); + ok1(tdb); + + /* Tickle bug on appending zero length buffer to zero length buffer. */ + key.dsize = strlen("hi"); + key.dptr = (void *)"hi"; + data.dptr = (void *)"world"; + data.dsize = strlen("world"); + + ok1(tdb_store(tdb, key, data, TDB_INSERT) == 0); + + ok1(tdb_transaction_start(tdb) == 0); + ok(tdb->have_transaction_lock, "Transaction lock in transaction"); + tdb_traverse(tdb, traverse, NULL); + + /* That should *not* release the transaction lock! */ + ok(tdb->have_transaction_lock, "Transaction lock after traverse"); + tdb_traverse_read(tdb, traverse, NULL); + + /* That should *not* release the transaction lock! */ + ok(tdb->have_transaction_lock, "Transaction lock after traverse_read"); + ok1(tdb_transaction_commit(tdb) == 0); + ok(!tdb->have_transaction_lock, "Transaction unlock"); + + tdb_close(tdb); + + return exit_status(); +} diff --git a/ccan/tdb/test/run-zero-append.c b/ccan/tdb/test/run-zero-append.c new file mode 100644 index 00000000..287d74c3 --- /dev/null +++ b/ccan/tdb/test/run-zero-append.c @@ -0,0 +1,37 @@ +#define _XOPEN_SOURCE 500 +#include "tdb/tdb.h" +#include "tdb/io.c" +#include "tdb/tdb.c" +#include "tdb/lock.c" +#include "tdb/freelist.c" +#include "tdb/traverse.c" +#include "tdb/transaction.c" +#include "tdb/error.c" +#include "tdb/open.c" +#include "tap/tap.h" +#include +#include + +int main(int argc, char *argv[]) +{ + struct tdb_context *tdb; + TDB_DATA key, data; + + plan_tests(4); + tdb = tdb_open(NULL, 1024, TDB_INTERNAL, O_CREAT|O_TRUNC|O_RDWR, 0600); + ok1(tdb); + + /* Tickle bug on appending zero length buffer to zero length buffer. */ + key.dsize = strlen("hi"); + key.dptr = (void *)"hi"; + data.dptr = (void *)"world"; + data.dsize = 0; + + ok1(tdb_append(tdb, key, data) == 0); + ok1(tdb_append(tdb, key, data) == 0); + data = tdb_fetch(tdb, key); + ok1(data.dsize == 0); + tdb_close(tdb); + + return exit_status(); +} diff --git a/ccan/tdb/tools/Makefile b/ccan/tdb/tools/Makefile new file mode 100644 index 00000000..d52b9f37 --- /dev/null +++ b/ccan/tdb/tools/Makefile @@ -0,0 +1,29 @@ +LDLIBS:=-lccan +CFLAGS:=-I../../.. -Wall -O3 #-g -pg +LDFLAGS:=-L../../.. + +default: replay_trace tdbtorture tdbdump + +replay_trace: replay_trace.c keywords.c + $(LINK.c) $< $(LOADLIBES) $(LDLIBS) -o $@ + +keywords.c: keywords.gperf + gperf $< > $@ + +check: replay_trace + @rm -f *.reduced_trace + @set -e; for f in tests/*.trace.tar.bz2; do \ + tar xvfj $$f; \ + ./replay_trace replay.tdb *.reduced_trace; \ + rm -f *.reduced_trace; \ + done + +# Usage: make mytest.trace.tar.bz2 TRACEFILES=*.trace +%.trace.tar.bz2: $(patsubst %.trace,%.reduced_trace,$(wildcard $(TRACEFILES))) + tar cvfj $@ $^ + +%.reduced_trace: %.trace + @sed 's/\(^[0-9]* traverse\) .*/\1fn/' < $^ > $@ + +clean: + rm -f replay_trace tdbtorture tdbdump *.o diff --git a/ccan/tdb/tools/keywords.c b/ccan/tdb/tools/keywords.c new file mode 100644 index 00000000..461a61e7 --- /dev/null +++ b/ccan/tdb/tools/keywords.c @@ -0,0 +1,197 @@ +/* ANSI-C code produced by gperf version 3.0.3 */ +/* Command-line: gperf keywords.gperf */ +/* Computed positions: -k'5,$' */ + +#if !((' ' == 32) && ('!' == 33) && ('"' == 34) && ('#' == 35) \ + && ('%' == 37) && ('&' == 38) && ('\'' == 39) && ('(' == 40) \ + && (')' == 41) && ('*' == 42) && ('+' == 43) && (',' == 44) \ + && ('-' == 45) && ('.' == 46) && ('/' == 47) && ('0' == 48) \ + && ('1' == 49) && ('2' == 50) && ('3' == 51) && ('4' == 52) \ + && ('5' == 53) && ('6' == 54) && ('7' == 55) && ('8' == 56) \ + && ('9' == 57) && (':' == 58) && (';' == 59) && ('<' == 60) \ + && ('=' == 61) && ('>' == 62) && ('?' == 63) && ('A' == 65) \ + && ('B' == 66) && ('C' == 67) && ('D' == 68) && ('E' == 69) \ + && ('F' == 70) && ('G' == 71) && ('H' == 72) && ('I' == 73) \ + && ('J' == 74) && ('K' == 75) && ('L' == 76) && ('M' == 77) \ + && ('N' == 78) && ('O' == 79) && ('P' == 80) && ('Q' == 81) \ + && ('R' == 82) && ('S' == 83) && ('T' == 84) && ('U' == 85) \ + && ('V' == 86) && ('W' == 87) && ('X' == 88) && ('Y' == 89) \ + && ('Z' == 90) && ('[' == 91) && ('\\' == 92) && (']' == 93) \ + && ('^' == 94) && ('_' == 95) && ('a' == 97) && ('b' == 98) \ + && ('c' == 99) && ('d' == 100) && ('e' == 101) && ('f' == 102) \ + && ('g' == 103) && ('h' == 104) && ('i' == 105) && ('j' == 106) \ + && ('k' == 107) && ('l' == 108) && ('m' == 109) && ('n' == 110) \ + && ('o' == 111) && ('p' == 112) && ('q' == 113) && ('r' == 114) \ + && ('s' == 115) && ('t' == 116) && ('u' == 117) && ('v' == 118) \ + && ('w' == 119) && ('x' == 120) && ('y' == 121) && ('z' == 122) \ + && ('{' == 123) && ('|' == 124) && ('}' == 125) && ('~' == 126)) +/* The character set is not based on ISO-646. */ +#error "gperf generated tables don't work with this execution character set. Please report a bug to ." +#endif + +#line 1 "keywords.gperf" + +#line 4 "keywords.gperf" +struct op_table { + const char *name; + enum op_type type; + void (*enhance_op)(const char *filename, + struct op op[], unsigned int op_num, char *words[]); +}; +/* maximum key range = 43, duplicates = 0 */ + +#ifdef __GNUC__ +__inline +#else +#ifdef __cplusplus +inline +#endif +#endif +static unsigned int +hash_keyword (register const char *str, register unsigned int len) +{ + static const unsigned char asso_values[] = + { + 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, + 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, + 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, + 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, + 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, + 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, + 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, + 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, + 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, + 51, 51, 51, 51, 51, 51, 51, 20, 51, 25, + 5, 0, 0, 5, 5, 51, 51, 0, 0, 0, + 20, 51, 20, 51, 51, 0, 5, 0, 51, 0, + 51, 5, 51, 51, 51, 51, 51, 51, 51, 51, + 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, + 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, + 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, + 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, + 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, + 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, + 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, + 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, + 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, + 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, + 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, + 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, + 51, 51, 51, 51, 51, 51 + }; + return len + asso_values[(unsigned char)str[4]] + asso_values[(unsigned char)str[len - 1]]; +} + +#ifdef __GNUC__ +__inline +#ifdef __GNUC_STDC_INLINE__ +__attribute__ ((__gnu_inline__)) +#endif +#endif +const struct op_table * +find_keyword (register const char *str, register unsigned int len) +{ + enum + { + TOTAL_KEYWORDS = 33, + MIN_WORD_LENGTH = 8, + MAX_WORD_LENGTH = 25, + MIN_HASH_VALUE = 8, + MAX_HASH_VALUE = 50 + }; + + static const struct op_table wordlist[] = + { + {""}, {""}, {""}, {""}, {""}, {""}, {""}, {""}, +#line 43 "keywords.gperf" + {"traverse", OP_TDB_TRAVERSE, op_add_traverse,}, +#line 33 "keywords.gperf" + {"tdb_store", OP_TDB_STORE, op_add_store,}, +#line 32 "keywords.gperf" + {"tdb_exists", OP_TDB_EXISTS, op_add_key_ret,}, +#line 16 "keywords.gperf" + {"tdb_lockall", OP_TDB_LOCKALL, op_add_nothing,}, +#line 36 "keywords.gperf" + {"tdb_wipe_all", OP_TDB_WIPE_ALL, op_add_nothing,}, +#line 20 "keywords.gperf" + {"tdb_unlockall", OP_TDB_UNLOCKALL, op_add_nothing,}, +#line 47 "keywords.gperf" + {"tdb_fetch", OP_TDB_FETCH, op_add_key_data,}, +#line 48 "keywords.gperf" + {"tdb_delete", OP_TDB_DELETE, op_add_key_ret,}, +#line 17 "keywords.gperf" + {"tdb_lockall_mark", OP_TDB_LOCKALL_MARK, op_add_nothing,}, +#line 45 "keywords.gperf" + {"tdb_firstkey", OP_TDB_FIRSTKEY, op_add_key,}, +#line 18 "keywords.gperf" + {"tdb_lockall_unmark", OP_TDB_LOCKALL_UNMARK, op_add_nothing,}, +#line 35 "keywords.gperf" + {"tdb_get_seqnum", OP_TDB_GET_SEQNUM, op_add_seqnum,}, +#line 19 "keywords.gperf" + {"tdb_lockall_nonblock", OP_TDB_LOCKALL_NONBLOCK, op_add_nothing,}, +#line 21 "keywords.gperf" + {"tdb_lockall_read", OP_TDB_LOCKALL_READ, op_add_nothing,}, + {""}, +#line 23 "keywords.gperf" + {"tdb_unlockall_read", OP_TDB_UNLOCKALL_READ, op_add_nothing,}, + {""}, +#line 22 "keywords.gperf" + {"tdb_lockall_read_nonblock", OP_TDB_LOCKALL_READ_NONBLOCK, op_add_nothing,}, +#line 42 "keywords.gperf" + {"tdb_traverse_end", OP_TDB_TRAVERSE_END, op_analyze_traverse,}, +#line 38 "keywords.gperf" + {"tdb_transaction_cancel", OP_TDB_TRANSACTION_CANCEL, op_analyze_transaction,}, +#line 41 "keywords.gperf" + {"tdb_traverse_start", OP_TDB_TRAVERSE_START, op_add_traverse_start,}, + {""}, +#line 44 "keywords.gperf" + {"traversefn", OP_TDB_TRAVERSE, op_add_traversefn,}, +#line 37 "keywords.gperf" + {"tdb_transaction_start", OP_TDB_TRANSACTION_START, op_add_transaction,}, +#line 39 "keywords.gperf" + {"tdb_transaction_commit", OP_TDB_TRANSACTION_COMMIT, op_analyze_transaction,}, +#line 40 "keywords.gperf" + {"tdb_traverse_read_start", OP_TDB_TRAVERSE_READ_START, op_add_traverse_start,}, + {""}, +#line 34 "keywords.gperf" + {"tdb_append", OP_TDB_APPEND, op_add_append,}, +#line 46 "keywords.gperf" + {"tdb_nextkey", OP_TDB_NEXTKEY, op_add_key_data,}, + {""}, +#line 24 "keywords.gperf" + {"tdb_chainlock", OP_TDB_CHAINLOCK, op_add_chainlock,}, + {""}, +#line 28 "keywords.gperf" + {"tdb_chainunlock", OP_TDB_CHAINUNLOCK, op_analyze_chainlock,}, +#line 31 "keywords.gperf" + {"tdb_parse_record", OP_TDB_PARSE_RECORD, op_add_key_ret,}, + {""}, +#line 26 "keywords.gperf" + {"tdb_chainlock_mark", OP_TDB_CHAINLOCK_MARK, op_add_key,}, + {""}, +#line 27 "keywords.gperf" + {"tdb_chainlock_unmark", OP_TDB_CHAINLOCK_UNMARK, op_add_key,}, + {""}, +#line 25 "keywords.gperf" + {"tdb_chainlock_nonblock", OP_TDB_CHAINLOCK_NONBLOCK, op_add_chainlock_ret,}, +#line 29 "keywords.gperf" + {"tdb_chainlock_read", OP_TDB_CHAINLOCK_READ, op_add_chainlock,}, + {""}, +#line 30 "keywords.gperf" + {"tdb_chainunlock_read", OP_TDB_CHAINUNLOCK_READ, op_analyze_chainlock,} + }; + + if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH) + { + register int key = hash_keyword (str, len); + + if (key <= MAX_HASH_VALUE && key >= 0) + { + register const char *s = wordlist[key].name; + + if (*str == *s && !strcmp (str + 1, s + 1)) + return &wordlist[key]; + } + } + return 0; +} diff --git a/ccan/tdb/tools/keywords.gperf b/ccan/tdb/tools/keywords.gperf new file mode 100644 index 00000000..676b64e6 --- /dev/null +++ b/ccan/tdb/tools/keywords.gperf @@ -0,0 +1,48 @@ +%{ +%} +%language=ANSI-C +struct op_table { + const char *name; + enum op_type type; + void (*enhance_op)(const char *filename, + struct op op[], unsigned int op_num, char *words[]); +}; +%define hash-function-name hash_keyword +%define lookup-function-name find_keyword +%readonly-tables +%struct-type +%enum +%% +tdb_lockall, OP_TDB_LOCKALL, op_add_nothing, +tdb_lockall_mark, OP_TDB_LOCKALL_MARK, op_add_nothing, +tdb_lockall_unmark, OP_TDB_LOCKALL_UNMARK, op_add_nothing, +tdb_lockall_nonblock, OP_TDB_LOCKALL_NONBLOCK, op_add_nothing, +tdb_unlockall, OP_TDB_UNLOCKALL, op_add_nothing, +tdb_lockall_read, OP_TDB_LOCKALL_READ, op_add_nothing, +tdb_lockall_read_nonblock, OP_TDB_LOCKALL_READ_NONBLOCK, op_add_nothing, +tdb_unlockall_read, OP_TDB_UNLOCKALL_READ, op_add_nothing, +tdb_chainlock, OP_TDB_CHAINLOCK, op_add_chainlock, +tdb_chainlock_nonblock, OP_TDB_CHAINLOCK_NONBLOCK, op_add_chainlock_ret, +tdb_chainlock_mark, OP_TDB_CHAINLOCK_MARK, op_add_key, +tdb_chainlock_unmark, OP_TDB_CHAINLOCK_UNMARK, op_add_key, +tdb_chainunlock, OP_TDB_CHAINUNLOCK, op_analyze_chainlock, +tdb_chainlock_read, OP_TDB_CHAINLOCK_READ, op_add_chainlock, +tdb_chainunlock_read, OP_TDB_CHAINUNLOCK_READ, op_analyze_chainlock, +tdb_parse_record, OP_TDB_PARSE_RECORD, op_add_key_ret, +tdb_exists, OP_TDB_EXISTS, op_add_key_ret, +tdb_store, OP_TDB_STORE, op_add_store, +tdb_append, OP_TDB_APPEND, op_add_append, +tdb_get_seqnum, OP_TDB_GET_SEQNUM, op_add_seqnum, +tdb_wipe_all, OP_TDB_WIPE_ALL, op_add_nothing, +tdb_transaction_start, OP_TDB_TRANSACTION_START, op_add_transaction, +tdb_transaction_cancel, OP_TDB_TRANSACTION_CANCEL, op_analyze_transaction, +tdb_transaction_commit, OP_TDB_TRANSACTION_COMMIT, op_analyze_transaction, +tdb_traverse_read_start, OP_TDB_TRAVERSE_READ_START, op_add_traverse_start, +tdb_traverse_start, OP_TDB_TRAVERSE_START, op_add_traverse_start, +tdb_traverse_end, OP_TDB_TRAVERSE_END, op_analyze_traverse, +traverse, OP_TDB_TRAVERSE, op_add_traverse, +traversefn, OP_TDB_TRAVERSE, op_add_traversefn, +tdb_firstkey, OP_TDB_FIRSTKEY, op_add_key, +tdb_nextkey, OP_TDB_NEXTKEY, op_add_key_data, +tdb_fetch, OP_TDB_FETCH, op_add_key_data, +tdb_delete, OP_TDB_DELETE, op_add_key_ret, diff --git a/ccan/tdb/tools/replay_trace.c b/ccan/tdb/tools/replay_trace.c new file mode 100644 index 00000000..67809d82 --- /dev/null +++ b/ccan/tdb/tools/replay_trace.c @@ -0,0 +1,1795 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#define STRINGIFY2(x) #x +#define STRINGIFY(x) STRINGIFY2(x) + +/* Avoid mod by zero */ +static unsigned int total_keys = 1; + +/* #define DEBUG_DEPS 1 */ + +/* Traversals block transactions in the current implementation. */ +#define TRAVERSALS_TAKE_TRANSACTION_LOCK 1 + +struct pipe { + int fd[2]; +}; +static struct pipe *pipes; +static int backoff_fd = -1; + +static void __attribute__((noreturn)) fail(const char *filename, + unsigned int line, + const char *fmt, ...) +{ + va_list ap; + + va_start(ap, fmt); + fprintf(stderr, "%s:%u: FAIL: ", filename, line); + vfprintf(stderr, fmt, ap); + fprintf(stderr, "\n"); + va_end(ap); + exit(1); +} + +/* Try or die. */ +#define try(expr, expect) \ + do { \ + int ret = (expr); \ + if (ret != (expect)) \ + fail(filename[file], i+1, \ + STRINGIFY(expr) "= %i", ret); \ + } while (0) + +/* Try or imitate results. */ +#define unreliable(expr, expect, force, undo) \ + do { \ + int ret = expr; \ + if (ret != expect) { \ + fprintf(stderr, "%s:%u: %s gave %i not %i", \ + filename[file], i+1, STRINGIFY(expr), \ + ret, expect); \ + if (expect == 0) \ + force; \ + else \ + undo; \ + } \ + } while (0) + +static bool key_eq(TDB_DATA a, TDB_DATA b) +{ + if (a.dsize != b.dsize) + return false; + return memcmp(a.dptr, b.dptr, a.dsize) == 0; +} + +/* This is based on the hash algorithm from gdbm */ +static unsigned int hash_key(TDB_DATA *key) +{ + uint32_t value; /* Used to compute the hash value. */ + uint32_t i; /* Used to cycle through random values. */ + + /* Set the initial value from the key size. */ + for (value = 0x238F13AF ^ key->dsize, i=0; i < key->dsize; i++) + value = (value + (key->dptr[i] << (i*5 % 24))); + + return (1103515243 * value + 12345); +} + +enum op_type { + OP_TDB_LOCKALL, + OP_TDB_LOCKALL_MARK, + OP_TDB_LOCKALL_UNMARK, + OP_TDB_LOCKALL_NONBLOCK, + OP_TDB_UNLOCKALL, + OP_TDB_LOCKALL_READ, + OP_TDB_LOCKALL_READ_NONBLOCK, + OP_TDB_UNLOCKALL_READ, + OP_TDB_CHAINLOCK, + OP_TDB_CHAINLOCK_NONBLOCK, + OP_TDB_CHAINLOCK_MARK, + OP_TDB_CHAINLOCK_UNMARK, + OP_TDB_CHAINUNLOCK, + OP_TDB_CHAINLOCK_READ, + OP_TDB_CHAINUNLOCK_READ, + OP_TDB_PARSE_RECORD, + OP_TDB_EXISTS, + OP_TDB_STORE, + OP_TDB_APPEND, + OP_TDB_GET_SEQNUM, + OP_TDB_WIPE_ALL, + OP_TDB_TRANSACTION_START, + OP_TDB_TRANSACTION_CANCEL, + OP_TDB_TRANSACTION_COMMIT, + OP_TDB_TRAVERSE_READ_START, + OP_TDB_TRAVERSE_START, + OP_TDB_TRAVERSE_END, + OP_TDB_TRAVERSE, + OP_TDB_TRAVERSE_END_EARLY, + OP_TDB_FIRSTKEY, + OP_TDB_NEXTKEY, + OP_TDB_FETCH, + OP_TDB_DELETE, +}; + +struct op { + unsigned int seqnum; + enum op_type type; + TDB_DATA key; + TDB_DATA data; + int ret; + + /* Who is waiting for us? */ + struct list_head post; + /* What are we waiting for? */ + struct list_head pre; + + /* If I'm part of a group (traverse/transaction) where is + * start? (Otherwise, 0) */ + unsigned int group_start; + + union { + int flag; /* open and store */ + struct { /* append */ + TDB_DATA pre; + TDB_DATA post; + } append; + /* transaction/traverse start/chainlock */ + unsigned int group_len; + }; +}; + +struct op_desc { + unsigned int file; + unsigned int op_num; +}; + +static unsigned char hex_char(const char *filename, unsigned int line, char c) +{ + c = toupper(c); + if (c >= 'A' && c <= 'F') + return c - 'A' + 10; + if (c >= '0' && c <= '9') + return c - '0'; + fail(filename, line, "invalid hex character '%c'", c); +} + +/* TDB data is :<%02x>* */ +static TDB_DATA make_tdb_data(const void *ctx, + const char *filename, unsigned int line, + const char *word) +{ + TDB_DATA data; + unsigned int i; + const char *p; + + if (streq(word, "NULL")) + return tdb_null; + + data.dsize = atoi(word); + data.dptr = talloc_array(ctx, unsigned char, data.dsize); + p = strchr(word, ':'); + if (!p) + fail(filename, line, "invalid tdb data '%s'", word); + p++; + for (i = 0; i < data.dsize; i++) + data.dptr[i] = hex_char(filename, line, p[i*2])*16 + + hex_char(filename, line, p[i*2+1]); + + return data; +} + +static void add_op(const char *filename, struct op **op, unsigned int i, + unsigned int seqnum, enum op_type type) +{ + struct op *new; + *op = talloc_realloc(NULL, *op, struct op, i+1); + new = (*op) + i; + new->type = type; + new->seqnum = seqnum; + new->ret = 0; + new->group_start = 0; +} + +static void op_add_nothing(const char *filename, + struct op op[], unsigned int op_num, char *words[]) +{ + if (words[2]) + fail(filename, op_num+1, "Expected no arguments"); + op[op_num].key = tdb_null; +} + +static void op_add_key(const char *filename, + struct op op[], unsigned int op_num, char *words[]) +{ + if (words[2] == NULL || words[3]) + fail(filename, op_num+1, "Expected just a key"); + + op[op_num].key = make_tdb_data(op, filename, op_num+1, words[2]); + total_keys++; +} + +static void op_add_key_ret(const char *filename, + struct op op[], unsigned int op_num, char *words[]) +{ + if (!words[2] || !words[3] || !words[4] || words[5] + || !streq(words[3], "=")) + fail(filename, op_num+1, "Expected = "); + op[op_num].ret = atoi(words[4]); + op[op_num].key = make_tdb_data(op, filename, op_num+1, words[2]); + /* May only be a unique key if it fails */ + if (op[op_num].ret != 0) + total_keys++; +} + +static void op_add_key_data(const char *filename, + struct op op[], unsigned int op_num, char *words[]) +{ + if (!words[2] || !words[3] || !words[4] || words[5] + || !streq(words[3], "=")) + fail(filename, op_num+1, "Expected = "); + op[op_num].key = make_tdb_data(op, filename, op_num+1, words[2]); + op[op_num].data = make_tdb_data(op, filename, op_num+1, words[4]); + /* May only be a unique key if it fails */ + if (!op[op_num].data.dptr) + total_keys++; +} + +/* We don't record the keys or data for a traverse, as we don't use them. */ +static void op_add_traverse(const char *filename, + struct op op[], unsigned int op_num, char *words[]) +{ + if (!words[2] || !words[3] || !words[4] || words[5] + || !streq(words[3], "=")) + fail(filename, op_num+1, "Expected = "); + op[op_num].key = tdb_null; +} + +/* Full traverse info is useful for debugging, but changing it to + * "traversefn" without the data makes the traces *much* smaller! */ +static void op_add_traversefn(const char *filename, + struct op op[], unsigned int op_num, char *words[]) +{ + if (words[2]) + fail(filename, op_num+1, "Expected no values"); + op[op_num].key = tdb_null; +} + +/* tdb_store = */ +static void op_add_store(const char *filename, + struct op op[], unsigned int op_num, char *words[]) +{ + if (!words[2] || !words[3] || !words[4] || !words[5] || !words[6] + || words[7] || !streq(words[5], "=")) + fail(filename, op_num+1, "Expect = "); + + op[op_num].flag = strtoul(words[4], NULL, 0); + op[op_num].ret = atoi(words[6]); + op[op_num].key = make_tdb_data(op, filename, op_num+1, words[2]); + op[op_num].data = make_tdb_data(op, filename, op_num+1, words[3]); + total_keys++; +} + +/* tdb_append = */ +static void op_add_append(const char *filename, + struct op op[], unsigned int op_num, char *words[]) +{ + if (!words[2] || !words[3] || !words[4] || !words[5] || words[6] + || !streq(words[4], "=")) + fail(filename, op_num+1, "Expect = "); + + op[op_num].key = make_tdb_data(op, filename, op_num+1, words[2]); + op[op_num].data = make_tdb_data(op, filename, op_num+1, words[3]); + + op[op_num].append.post + = make_tdb_data(op, filename, op_num+1, words[5]); + + /* By subtraction, figure out what previous data was. */ + op[op_num].append.pre.dptr = op[op_num].append.post.dptr; + op[op_num].append.pre.dsize + = op[op_num].append.post.dsize - op[op_num].data.dsize; + total_keys++; +} + +/* tdb_get_seqnum = */ +static void op_add_seqnum(const char *filename, + struct op op[], unsigned int op_num, char *words[]) +{ + if (!words[2] || !words[3] || words[4] || !streq(words[2], "=")) + fail(filename, op_num+1, "Expect = "); + + op[op_num].key = tdb_null; + op[op_num].ret = atoi(words[3]); +} + +static void op_add_traverse_start(const char *filename, + struct op op[], + unsigned int op_num, char *words[]) +{ + if (words[2]) + fail(filename, op_num+1, "Expect no arguments"); + + op[op_num].key = tdb_null; + op[op_num].group_len = 0; +} + +static void op_add_transaction(const char *filename, struct op op[], + unsigned int op_num, char *words[]) +{ + if (words[2]) + fail(filename, op_num+1, "Expect no arguments"); + + op[op_num].key = tdb_null; + op[op_num].group_len = 0; +} + +static void op_add_chainlock(const char *filename, + struct op op[], unsigned int op_num, char *words[]) +{ + if (words[2] == NULL || words[3]) + fail(filename, op_num+1, "Expected just a key"); + + /* A chainlock key isn't a key in the normal sense; it doesn't + * have to be in the db at all. Also, we don't want to hash this op. */ + op[op_num].data = make_tdb_data(op, filename, op_num+1, words[2]); + op[op_num].key = tdb_null; + op[op_num].group_len = 0; +} + +static void op_add_chainlock_ret(const char *filename, + struct op op[], unsigned int op_num, + char *words[]) +{ + if (!words[2] || !words[3] || !words[4] || words[5] + || !streq(words[3], "=")) + fail(filename, op_num+1, "Expected = "); + op[op_num].ret = atoi(words[4]); + op[op_num].data = make_tdb_data(op, filename, op_num+1, words[2]); + op[op_num].key = tdb_null; + op[op_num].group_len = 0; + total_keys++; +} + +static int op_find_start(struct op op[], unsigned int op_num, enum op_type type) +{ + unsigned int i; + + for (i = op_num-1; i > 0; i--) { + if (op[i].type == type && !op[i].group_len) + return i; + } + return 0; +} + +static void op_analyze_transaction(const char *filename, + struct op op[], unsigned int op_num, + char *words[]) +{ + unsigned int start, i; + + op[op_num].key = tdb_null; + + if (words[2]) + fail(filename, op_num+1, "Expect no arguments"); + + start = op_find_start(op, op_num, OP_TDB_TRANSACTION_START); + if (!start) + fail(filename, op_num+1, "no transaction start found"); + + op[start].group_len = op_num - start; + + /* This rolls in nested transactions. I think that's right. */ + for (i = start; i <= op_num; i++) + op[i].group_start = start; +} + +/* We treat chainlocks a lot like transactions, even though that's overkill */ +static void op_analyze_chainlock(const char *filename, + struct op op[], unsigned int op_num, + char *words[]) +{ + unsigned int i, start; + + if (words[2] == NULL || words[3]) + fail(filename, op_num+1, "Expected just a key"); + + op[op_num].data = make_tdb_data(op, filename, op_num+1, words[2]); + op[op_num].key = tdb_null; + total_keys++; + + start = op_find_start(op, op_num, OP_TDB_CHAINLOCK); + if (!start) + start = op_find_start(op, op_num, OP_TDB_CHAINLOCK_READ); + if (!start) + fail(filename, op_num+1, "no initial chainlock found"); + + /* FIXME: We'd have to do something clever to make this work + * vs. deadlock. */ + if (!key_eq(op[start].data, op[op_num].data)) + fail(filename, op_num+1, "nested chainlock calls?"); + + op[start].group_len = op_num - start; + for (i = start; i <= op_num; i++) + op[i].group_start = start; +} + +static void op_analyze_traverse(const char *filename, + struct op op[], unsigned int op_num, + char *words[]) +{ + int i, start; + + op[op_num].key = tdb_null; + + /* = %u means traverse function terminated. */ + if (words[2]) { + if (!streq(words[2], "=") || !words[3] || words[4]) + fail(filename, op_num+1, "expect = "); + op[op_num].ret = atoi(words[3]); + } else + op[op_num].ret = 0; + + start = op_find_start(op, op_num, OP_TDB_TRAVERSE_START); + if (!start) + start = op_find_start(op, op_num, OP_TDB_TRAVERSE_READ_START); + if (!start) + fail(filename, op_num+1, "no traversal start found"); + + op[start].group_len = op_num - start; + + /* Don't roll in nested traverse/chainlock */ + for (i = start; i <= op_num; i++) + if (!op[i].group_start) + op[i].group_start = start; +} + +/* Keep -Wmissing-declarations happy: */ +const struct op_table * +find_keyword (register const char *str, register unsigned int len); + +#include "keywords.c" + +struct depend { + /* We can have more than one */ + struct list_node pre_list; + struct list_node post_list; + struct op_desc needs; + struct op_desc prereq; +}; + +static void check_deps(const char *filename, struct op op[], unsigned int num) +{ +#ifdef DEBUG_DEPS + unsigned int i; + + for (i = 1; i < num; i++) + if (!list_empty(&op[i].pre)) + fail(filename, i+1, "Still has dependencies"); +#endif +} + +static void dump_pre(char *filename[], struct op *op[], + unsigned int file, unsigned int i) +{ + struct depend *dep; + + printf("%s:%u (%u) still waiting for:\n", filename[file], i+1, + op[file][i].seqnum); + list_for_each(&op[file][i].pre, dep, pre_list) + printf(" %s:%u (%u)\n", + filename[dep->prereq.file], dep->prereq.op_num+1, + op[dep->prereq.file][dep->prereq.op_num].seqnum); + check_deps(filename[file], op[file], i); +} + +/* We simply read/write pointers, since we all are children. */ +static bool do_pre(struct tdb_context *tdb, + char *filename[], struct op *op[], + unsigned int file, int pre_fd, unsigned int i, + bool backoff) +{ + while (!list_empty(&op[file][i].pre)) { + struct depend *dep; + +#if DEBUG_DEPS + printf("%s:%u:waiting for pre\n", filename[file], i+1); + fflush(stdout); +#endif + if (backoff) + alarm(2); + else + alarm(10); + while (read(pre_fd, &dep, sizeof(dep)) != sizeof(dep)) { + if (errno == EINTR) { + if (backoff) { + struct op_desc desc = { file,i }; + warnx("%s:%u:avoiding deadlock", + filename[file], i+1); + if (write(backoff_fd, &desc, + sizeof(desc)) != sizeof(desc)) + err(1, "writing backoff_fd"); + return false; + } + dump_pre(filename, op, file, i); + exit(1); + } else + errx(1, "Reading from pipe"); + } + alarm(0); + +#if DEBUG_DEPS + printf("%s:%u:got pre %u from %s:%u\n", filename[file], i+1, + dep->needs.op_num+1, filename[dep->prereq.file], + dep->prereq.op_num+1); + fflush(stdout); +#endif + /* This could be any op, not just this one. */ + talloc_free(dep); + } + return true; +} + +static void do_post(char *filename[], struct op *op[], + unsigned int file, unsigned int i) +{ + struct depend *dep; + + list_for_each(&op[file][i].post, dep, post_list) { +#if DEBUG_DEPS + printf("%s:%u:sending to file %s:%u\n", filename[file], i+1, + filename[dep->needs.file], dep->needs.op_num+1); +#endif + if (write(pipes[dep->needs.file].fd[1], &dep, sizeof(dep)) + != sizeof(dep)) + err(1, "%s:%u failed to tell file %s", + filename[file], i+1, filename[dep->needs.file]); + } +} + +static int get_len(TDB_DATA key, TDB_DATA data, void *private_data) +{ + return data.dsize; +} + +static unsigned run_ops(struct tdb_context *tdb, + int pre_fd, + char *filename[], + struct op *op[], + unsigned int file, + unsigned int start, unsigned int stop, + bool backoff); + +struct traverse_info { + struct op **op; + char **filename; + unsigned file; + int pre_fd; + unsigned int start; + unsigned int i; +}; + +/* More complex. Just do whatever's they did at the n'th entry. */ +static int nontrivial_traverse(struct tdb_context *tdb, + TDB_DATA key, TDB_DATA data, + void *_tinfo) +{ + struct traverse_info *tinfo = _tinfo; + unsigned int trav_len = tinfo->op[tinfo->file][tinfo->start].group_len; + bool avoid_deadlock = false; + + if (tinfo->i == tinfo->start + trav_len) { + /* This can happen if traverse expects to be empty. */ + if (trav_len == 1) + return 1; + fail(tinfo->filename[tinfo->file], tinfo->start + 1, + "traverse did not terminate"); + } + + if (tinfo->op[tinfo->file][tinfo->i].type != OP_TDB_TRAVERSE) + fail(tinfo->filename[tinfo->file], tinfo->start + 1, + "%s:%u:traverse terminated early"); + +#if TRAVERSALS_TAKE_TRANSACTION_LOCK + avoid_deadlock = true; +#endif + + /* Run any normal ops. */ + tinfo->i = run_ops(tdb, tinfo->pre_fd, tinfo->filename, tinfo->op, + tinfo->file, tinfo->i+1, tinfo->start + trav_len, + avoid_deadlock); + + /* We backed off, or we hit OP_TDB_TRAVERSE_END/EARLY. */ + if (tinfo->op[tinfo->file][tinfo->i].type != OP_TDB_TRAVERSE) + return 1; + + return 0; +} + +static unsigned op_traverse(struct tdb_context *tdb, + int pre_fd, + char *filename[], + unsigned int file, + int (*traversefn)(struct tdb_context *, + tdb_traverse_func, void *), + struct op *op[], + unsigned int start) +{ + struct traverse_info tinfo = { op, filename, file, pre_fd, + start, start+1 }; + + traversefn(tdb, nontrivial_traverse, &tinfo); + + /* Traversing in wrong order can have strange effects: eg. if + * original traverse went A (delete A), B, we might do B + * (delete A). So if we have ops left over, we do it now. */ + while (tinfo.i != start + op[file][start].group_len) { + if (op[file][tinfo.i].type == OP_TDB_TRAVERSE + || op[file][tinfo.i].type == OP_TDB_TRAVERSE_END_EARLY) + tinfo.i++; + else + tinfo.i = run_ops(tdb, pre_fd, filename, op, file, + tinfo.i, + start + op[file][start].group_len, + false); + } + + return tinfo.i; +} + +static void break_out(int sig) +{ +} + +static __attribute__((noinline)) +unsigned run_ops(struct tdb_context *tdb, + int pre_fd, + char *filename[], + struct op *op[], + unsigned int file, + unsigned int start, unsigned int stop, + bool backoff) +{ + unsigned int i; + struct sigaction sa; + + sa.sa_handler = break_out; + sa.sa_flags = 0; + + sigaction(SIGALRM, &sa, NULL); + for (i = start; i < stop; i++) { + if (!do_pre(tdb, filename, op, file, pre_fd, i, backoff)) + return i; + + switch (op[file][i].type) { + case OP_TDB_LOCKALL: + try(tdb_lockall(tdb), op[file][i].ret); + break; + case OP_TDB_LOCKALL_MARK: + try(tdb_lockall_mark(tdb), op[file][i].ret); + break; + case OP_TDB_LOCKALL_UNMARK: + try(tdb_lockall_unmark(tdb), op[file][i].ret); + break; + case OP_TDB_LOCKALL_NONBLOCK: + unreliable(tdb_lockall_nonblock(tdb), op[file][i].ret, + tdb_lockall(tdb), tdb_unlockall(tdb)); + break; + case OP_TDB_UNLOCKALL: + try(tdb_unlockall(tdb), op[file][i].ret); + break; + case OP_TDB_LOCKALL_READ: + try(tdb_lockall_read(tdb), op[file][i].ret); + break; + case OP_TDB_LOCKALL_READ_NONBLOCK: + unreliable(tdb_lockall_read_nonblock(tdb), + op[file][i].ret, + tdb_lockall_read(tdb), + tdb_unlockall_read(tdb)); + break; + case OP_TDB_UNLOCKALL_READ: + try(tdb_unlockall_read(tdb), op[file][i].ret); + break; + case OP_TDB_CHAINLOCK: + try(tdb_chainlock(tdb, op[file][i].key), + op[file][i].ret); + break; + case OP_TDB_CHAINLOCK_NONBLOCK: + unreliable(tdb_chainlock_nonblock(tdb, op[file][i].key), + op[file][i].ret, + tdb_chainlock(tdb, op[file][i].key), + tdb_chainunlock(tdb, op[file][i].key)); + break; + case OP_TDB_CHAINLOCK_MARK: + try(tdb_chainlock_mark(tdb, op[file][i].key), + op[file][i].ret); + break; + case OP_TDB_CHAINLOCK_UNMARK: + try(tdb_chainlock_unmark(tdb, op[file][i].key), + op[file][i].ret); + break; + case OP_TDB_CHAINUNLOCK: + try(tdb_chainunlock(tdb, op[file][i].key), + op[file][i].ret); + break; + case OP_TDB_CHAINLOCK_READ: + try(tdb_chainlock_read(tdb, op[file][i].key), + op[file][i].ret); + break; + case OP_TDB_CHAINUNLOCK_READ: + try(tdb_chainunlock_read(tdb, op[file][i].key), + op[file][i].ret); + break; + case OP_TDB_PARSE_RECORD: + try(tdb_parse_record(tdb, op[file][i].key, get_len, + NULL), + op[file][i].ret); + break; + case OP_TDB_EXISTS: + try(tdb_exists(tdb, op[file][i].key), op[file][i].ret); + break; + case OP_TDB_STORE: + try(tdb_store(tdb, op[file][i].key, op[file][i].data, + op[file][i].flag), + op[file][i].ret); + break; + case OP_TDB_APPEND: + try(tdb_append(tdb, op[file][i].key, op[file][i].data), + op[file][i].ret); + break; + case OP_TDB_GET_SEQNUM: + try(tdb_get_seqnum(tdb), op[file][i].ret); + break; + case OP_TDB_WIPE_ALL: + try(tdb_wipe_all(tdb), op[file][i].ret); + break; + case OP_TDB_TRANSACTION_START: + try(tdb_transaction_start(tdb), op[file][i].ret); + break; + case OP_TDB_TRANSACTION_CANCEL: + try(tdb_transaction_cancel(tdb), op[file][i].ret); + break; + case OP_TDB_TRANSACTION_COMMIT: + try(tdb_transaction_commit(tdb), op[file][i].ret); + break; + case OP_TDB_TRAVERSE_READ_START: + i = op_traverse(tdb, pre_fd, filename, file, + tdb_traverse_read, op, i); + break; + case OP_TDB_TRAVERSE_START: + i = op_traverse(tdb, pre_fd, filename, file, + tdb_traverse, op, i); + break; + case OP_TDB_TRAVERSE: + case OP_TDB_TRAVERSE_END_EARLY: + /* Terminate: we're in a traverse, and we've + * done our ops. */ + return i; + case OP_TDB_TRAVERSE_END: + fail(filename[file], i+1, "unexpected end traverse"); + /* FIXME: These must be treated like traverse. */ + case OP_TDB_FIRSTKEY: + if (!key_eq(tdb_firstkey(tdb), op[file][i].data)) + fail(filename[file], i+1, "bad firstkey"); + break; + case OP_TDB_NEXTKEY: + if (!key_eq(tdb_nextkey(tdb, op[file][i].key), + op[file][i].data)) + fail(filename[file], i+1, "bad nextkey"); + break; + case OP_TDB_FETCH: { + TDB_DATA f = tdb_fetch(tdb, op[file][i].key); + if (!key_eq(f, op[file][i].data)) + fail(filename[file], i+1, "bad fetch %u", + f.dsize); + break; + } + case OP_TDB_DELETE: + try(tdb_delete(tdb, op[file][i].key), op[file][i].ret); + break; + } + do_post(filename, op, file, i); + } + return i; +} + +/* tdbtorture, in particular, can do a tdb_close with a transaction in + * progress. */ +static struct op *maybe_cancel_transaction(const char *filename, + struct op *op, unsigned int *num) +{ + unsigned int start = op_find_start(op, *num, OP_TDB_TRANSACTION_START); + + if (start) { + char *words[] = { "", "tdb_close", NULL }; + add_op(filename, &op, *num, op[start].seqnum, + OP_TDB_TRANSACTION_CANCEL); + op_analyze_transaction(filename, op, *num, words); + (*num)++; + } + return op; +} + +static struct op *load_tracefile(const char *filename, unsigned int *num, + unsigned int *hashsize, + unsigned int *tdb_flags, + unsigned int *open_flags) +{ + unsigned int i; + struct op *op = talloc_array(NULL, struct op, 1); + char **words; + char **lines; + char *file; + + file = grab_file(NULL, filename, NULL); + if (!file) + err(1, "Reading %s", filename); + + lines = strsplit(file, file, "\n", NULL); + if (!lines[0]) + errx(1, "%s is empty", filename); + + words = strsplit(lines, lines[0], " ", NULL); + if (!streq(words[1], "tdb_open")) + fail(filename, 1, "does not start with tdb_open"); + + *hashsize = atoi(words[2]); + *tdb_flags = strtoul(words[3], NULL, 0); + *open_flags = strtoul(words[4], NULL, 0); + + for (i = 1; lines[i]; i++) { + const struct op_table *opt; + + words = strsplit(lines, lines[i], " ", NULL); + if (!words[0] || !words[1]) + fail(filename, i+1, "Expected seqnum number and op"); + + opt = find_keyword(words[1], strlen(words[1])); + if (!opt) { + if (streq(words[1], "tdb_close")) { + if (lines[i+1]) + fail(filename, i+2, + "lines after tdb_close"); + *num = i; + talloc_free(lines); + return maybe_cancel_transaction(filename, + op, num); + } + fail(filename, i+1, "Unknown operation '%s'", words[1]); + } + + add_op(filename, &op, i, atoi(words[0]), opt->type); + opt->enhance_op(filename, op, i, words); + } + + fprintf(stderr, "%s:%u:last operation is not tdb_close: incomplete?", + filename, i); + talloc_free(lines); + *num = i - 1; + return maybe_cancel_transaction(filename, op, num); +} + +/* We remember all the keys we've ever seen, and who has them. */ +struct keyinfo { + TDB_DATA key; + unsigned int num_users; + struct op_desc *user; +}; + +static const TDB_DATA must_not_exist; +static const TDB_DATA must_exist; +static const TDB_DATA not_exists_or_empty; + +/* NULL means doesn't care if it exists or not, &must_exist means + * it must exist but we don't care what, &must_not_exist means it must + * not exist, otherwise the data it needs. */ +static const TDB_DATA *needs(const struct op *op) +{ + switch (op->type) { + /* FIXME: Pull forward deps, since we can deadlock */ + case OP_TDB_CHAINLOCK: + case OP_TDB_CHAINLOCK_NONBLOCK: + case OP_TDB_CHAINLOCK_MARK: + case OP_TDB_CHAINLOCK_UNMARK: + case OP_TDB_CHAINUNLOCK: + case OP_TDB_CHAINLOCK_READ: + case OP_TDB_CHAINUNLOCK_READ: + return NULL; + + case OP_TDB_APPEND: + if (op->append.pre.dsize == 0) + return ¬_exists_or_empty; + return &op->append.pre; + + case OP_TDB_STORE: + if (op->flag == TDB_INSERT) { + if (op->ret < 0) + return &must_exist; + else + return &must_not_exist; + } else if (op->flag == TDB_MODIFY) { + if (op->ret < 0) + return &must_not_exist; + else + return &must_exist; + } + /* No flags? Don't care */ + return NULL; + + case OP_TDB_EXISTS: + if (op->ret == 1) + return &must_exist; + else + return &must_not_exist; + + case OP_TDB_PARSE_RECORD: + if (op->ret < 0) + return &must_not_exist; + return &must_exist; + + /* FIXME: handle these. */ + case OP_TDB_WIPE_ALL: + case OP_TDB_FIRSTKEY: + case OP_TDB_NEXTKEY: + case OP_TDB_GET_SEQNUM: + case OP_TDB_TRAVERSE: + case OP_TDB_TRANSACTION_COMMIT: + case OP_TDB_TRANSACTION_CANCEL: + case OP_TDB_TRANSACTION_START: + return NULL; + + case OP_TDB_FETCH: + if (!op->data.dptr) + return &must_not_exist; + return &op->data; + + case OP_TDB_DELETE: + if (op->ret < 0) + return &must_not_exist; + return &must_exist; + + default: + errx(1, "Unexpected op type %i", op->type); + } + +} + +static bool starts_transaction(const struct op *op) +{ + return op->type == OP_TDB_TRANSACTION_START; +} + +static bool in_transaction(const struct op op[], unsigned int i) +{ + return op[i].group_start && starts_transaction(&op[op[i].group_start]); +} + +static bool successful_transaction(const struct op *op) +{ + return starts_transaction(op) + && op[op->group_len].type == OP_TDB_TRANSACTION_COMMIT; +} + +static bool starts_traverse(const struct op *op) +{ + return op->type == OP_TDB_TRAVERSE_START + || op->type == OP_TDB_TRAVERSE_READ_START; +} + +static bool in_traverse(const struct op op[], unsigned int i) +{ + return op[i].group_start && starts_traverse(&op[op[i].group_start]); +} + +static bool starts_chainlock(const struct op *op) +{ + return op->type == OP_TDB_CHAINLOCK_READ + || op->type == OP_TDB_CHAINLOCK; +} + +static bool in_chainlock(const struct op op[], unsigned int i) +{ + return op[i].group_start && starts_chainlock(&op[op[i].group_start]); +} + +/* What's the data after this op? pre if nothing changed. */ +static const TDB_DATA *gives(const TDB_DATA *key, const TDB_DATA *pre, + const struct op *op) +{ + if (starts_transaction(op) || starts_chainlock(op)) { + unsigned int i; + + /* Cancelled transactions don't change anything. */ + if (op[op->group_len].type == OP_TDB_TRANSACTION_CANCEL) + return pre; + assert(op[op->group_len].type == OP_TDB_TRANSACTION_COMMIT + || op[op->group_len].type == OP_TDB_CHAINUNLOCK_READ + || op[op->group_len].type == OP_TDB_CHAINUNLOCK); + + for (i = 1; i < op->group_len; i++) { + /* This skips nested transactions, too */ + if (key_eq(op[i].key, *key)) + pre = gives(key, pre, &op[i]); + } + return pre; + } + + /* Failed ops don't change state of db. */ + if (op->ret < 0) + return pre; + + if (op->type == OP_TDB_DELETE || op->type == OP_TDB_WIPE_ALL) + return &tdb_null; + + if (op->type == OP_TDB_APPEND) + return &op->append.post; + + if (op->type == OP_TDB_STORE) + return &op->data; + + return pre; +} + +static struct keyinfo *hash_ops(struct op *op[], unsigned int num_ops[], + unsigned int num) +{ + unsigned int i, j, h; + struct keyinfo *hash; + + hash = talloc_zero_array(op[0], struct keyinfo, total_keys*2); + for (i = 0; i < num; i++) { + for (j = 1; j < num_ops[i]; j++) { + /* We can't do this on allocation, due to realloc. */ + list_head_init(&op[i][j].post); + list_head_init(&op[i][j].pre); + + if (!op[i][j].key.dptr) + continue; + + h = hash_key(&op[i][j].key) % (total_keys * 2); + while (!key_eq(hash[h].key, op[i][j].key)) { + if (!hash[h].key.dptr) { + hash[h].key = op[i][j].key; + break; + } + h = (h + 1) % (total_keys * 2); + } + /* Might as well save some memory if we can. */ + if (op[i][j].key.dptr != hash[h].key.dptr) { + talloc_free(op[i][j].key.dptr); + op[i][j].key.dptr = hash[h].key.dptr; + } + hash[h].user = talloc_realloc(hash, hash[h].user, + struct op_desc, + hash[h].num_users+1); + + /* If it's in a transaction, it's the transaction which + * matters from an analysis POV. */ + if (in_transaction(op[i], j) + || in_chainlock(op[i], j)) { + unsigned start = op[i][j].group_start; + + /* Don't include twice. */ + if (hash[h].num_users + && hash[h].user[hash[h].num_users-1].file + == i + && hash[h].user[hash[h].num_users-1].op_num + == start) + continue; + + hash[h].user[hash[h].num_users].op_num = start; + } else + hash[h].user[hash[h].num_users].op_num = j; + hash[h].user[hash[h].num_users].file = i; + hash[h].num_users++; + } + } + + return hash; +} + +static bool satisfies(const TDB_DATA *key, const TDB_DATA *data, + const struct op *op) +{ + const TDB_DATA *need = NULL; + + if (starts_transaction(op) || starts_chainlock(op)) { + unsigned int i; + + /* Look through for an op in this transaction which + * needs this key. */ + for (i = 1; i < op->group_len; i++) { + if (key_eq(op[i].key, *key)) { + need = needs(&op[i]); + /* tdb_exists() is special: there might be + * something in the transaction with more + * specific requirements. Other ops don't have + * specific requirements (eg. store or delete), + * but they change the value so we can't get + * more information from future ops. */ + if (op[i].type != OP_TDB_EXISTS) + break; + } + } + } else + need = needs(op); + + /* Don't need anything? Cool. */ + if (!need) + return true; + + /* This should be tdb_null or a real value. */ + assert(data != &must_exist); + assert(data != &must_not_exist); + assert(data != ¬_exists_or_empty); + + /* Must not exist? data must not exist. */ + if (need == &must_not_exist) + return data == &tdb_null; + + /* Must exist? */ + if (need == &must_exist) + return data != &tdb_null; + + /* Either noexist or empty. */ + if (need == ¬_exists_or_empty) + return data->dsize == 0; + + /* Needs something specific. */ + return key_eq(*data, *need); +} + +static void move_to_front(struct op_desc res[], unsigned off, unsigned elem) +{ + if (elem != off) { + struct op_desc tmp = res[elem]; + memmove(res + off + 1, res + off, (elem - off)*sizeof(res[0])); + res[off] = tmp; + } +} + +static void restore_to_pos(struct op_desc res[], unsigned off, unsigned elem) +{ + if (elem != off) { + struct op_desc tmp = res[off]; + memmove(res + off, res + off + 1, (elem - off)*sizeof(res[0])); + res[elem] = tmp; + } +} + +static bool sort_deps(char *filename[], struct op *op[], + struct op_desc res[], + unsigned off, unsigned num, + const TDB_DATA *key, const TDB_DATA *data, + unsigned num_files, unsigned fuzz) +{ + unsigned int i, files_done; + struct op *this_op; + bool done[num_files]; + + /* None left? We're sorted. */ + if (off == num) + return true; + + /* Does this make sequence number go backwards? Allow a little fuzz. */ + if (off > 0) { + int seqnum1 = op[res[off-1].file][res[off-1].op_num].seqnum; + int seqnum2 = op[res[off].file][res[off].op_num].seqnum; + + if (seqnum1 - seqnum2 > (int)fuzz) { +#if DEBUG_DEPS + printf("Seqnum jump too far (%u -> %u)\n", + seqnum1, seqnum2); +#endif + return false; + } + } + + memset(done, 0, sizeof(done)); + + /* Since ops within a trace file are ordered, we just need to figure + * out which file to try next. Since we don't take into account + * inter-key relationships (which exist by virtue of trace file order), + * we minimize the chance of harm by trying to keep in seqnum order. */ + for (files_done = 0, i = off; i < num && files_done < num_files; i++) { + if (done[res[i].file]) + continue; + + this_op = &op[res[i].file][res[i].op_num]; + + /* Is what we have good enough for this op? */ + if (satisfies(key, data, this_op)) { + move_to_front(res, off, i); + if (sort_deps(filename, op, res, off+1, num, + key, gives(key, data, this_op), + num_files, fuzz)) + return true; + restore_to_pos(res, off, i); + } + done[res[i].file] = true; + files_done++; + } + + /* No combination worked. */ + return false; +} + +static void check_dep_sorting(struct op_desc user[], unsigned num_users, + unsigned num_files) +{ +#if DEBUG_DEPS + unsigned int i; + unsigned minima[num_files]; + + memset(minima, 0, sizeof(minima)); + for (i = 0; i < num_users; i++) { + assert(minima[user[i].file] < user[i].op_num); + minima[user[i].file] = user[i].op_num; + } +#endif +} + +/* All these ops happen on the same key. Which comes first? + * + * This can happen both because read ops or failed write ops don't + * change sequence number, and also due to race since we access the + * number unlocked (the race can cause less detectable ordering problems, + * in which case we'll deadlock and report: fix manually in that case). + */ +static void figure_deps(char *filename[], struct op *op[], + const TDB_DATA *key, struct op_desc user[], + unsigned num_users, unsigned num_files) +{ + /* We assume database starts empty. */ + const struct TDB_DATA *data = &tdb_null; + unsigned int fuzz; + + /* We prefer to keep strict seqnum order if possible: it's the + * most likely. We get more lax if that fails. */ + for (fuzz = 0; fuzz < 100; fuzz = (fuzz + 1)*2) { + if (sort_deps(filename, op, user, 0, num_users, key, data, + num_files, fuzz)) + break; + } + + if (fuzz >= 100) + fail(filename[user[0].file], user[0].op_num+1, + "Could not resolve inter-dependencies"); + + check_dep_sorting(user, num_users, num_files); +} + +static void sort_ops(struct keyinfo hash[], char *filename[], struct op *op[], + unsigned int num) +{ + unsigned int h; + + /* Gcc nexted function extension. How cool is this? */ + int compare_seqnum(const void *_a, const void *_b) + { + const struct op_desc *a = _a, *b = _b; + + /* First, maintain order within any trace file. */ + if (a->file == b->file) + return a->op_num - b->op_num; + + /* Otherwise, arrange by seqnum order. */ + if (op[a->file][a->op_num].seqnum != + op[b->file][b->op_num].seqnum) + return op[a->file][a->op_num].seqnum + - op[b->file][b->op_num].seqnum; + + /* Cancelled transactions are assumed to happen first. */ + if (starts_transaction(&op[a->file][a->op_num]) + && !successful_transaction(&op[a->file][a->op_num])) + return -1; + if (starts_transaction(&op[b->file][b->op_num]) + && !successful_transaction(&op[b->file][b->op_num])) + return 1; + + /* No idea. */ + return 0; + } + + /* Now sort into seqnum order. */ + for (h = 0; h < total_keys * 2; h++) { + struct op_desc *user = hash[h].user; + + qsort(user, hash[h].num_users, sizeof(user[0]), compare_seqnum); + figure_deps(filename, op, &hash[h].key, user, hash[h].num_users, + num); + } +} + +static int destroy_depend(struct depend *dep) +{ + list_del(&dep->pre_list); + list_del(&dep->post_list); + return 0; +} + +static void add_dependency(void *ctx, + struct op *op[], + char *filename[], + const struct op_desc *needs, + const struct op_desc *prereq) +{ + struct depend *dep; + + /* We don't depend on ourselves. */ + if (needs->file == prereq->file) { + assert(prereq->op_num < needs->op_num); + return; + } + +#if DEBUG_DEPS + printf("%s:%u: depends on %s:%u\n", + filename[needs->file], needs->op_num+1, + filename[prereq->file], prereq->op_num+1); +#endif + + dep = talloc(ctx, struct depend); + dep->needs = *needs; + dep->prereq = *prereq; + +#if TRAVERSALS_TAKE_TRANSACTION_LOCK + /* If something in a traverse depends on something in another + * traverse/transaction, it creates a dependency between the + * two groups. */ + if ((in_traverse(op[prereq->file], prereq->op_num) + && (starts_transaction(&op[needs->file][needs->op_num]) + || starts_traverse(&op[needs->file][needs->op_num]))) + || (in_traverse(op[needs->file], needs->op_num) + && (starts_transaction(&op[prereq->file][prereq->op_num]) + || starts_traverse(&op[prereq->file][prereq->op_num])))) { + unsigned int start; + + /* We are satisfied by end of group. */ + start = op[prereq->file][prereq->op_num].group_start; + dep->prereq.op_num = start + op[prereq->file][start].group_len; + /* And we need that done by start of our group. */ + dep->needs.op_num = op[needs->file][needs->op_num].group_start; + } + + /* There is also this case: + * ... + * ... + * Where if we start the traverse then wait, we could block + * the transaction and deadlock. + * + * We try to address this by ensuring that where seqnum indicates it's + * possible, we wait for before *starting* traverse. + */ + else if (in_traverse(op[needs->file], needs->op_num)) { + struct op *need = &op[needs->file][needs->op_num]; + if (op[needs->file][need->group_start].seqnum > + op[prereq->file][prereq->op_num].seqnum) { + dep->needs.op_num = need->group_start; + } + } +#endif + + /* If you depend on a transaction or chainlock, you actually + * depend on it ending. */ + if (starts_transaction(&op[prereq->file][dep->prereq.op_num]) + || starts_chainlock(&op[prereq->file][dep->prereq.op_num])) { + dep->prereq.op_num + += op[dep->prereq.file][dep->prereq.op_num].group_len; +#if DEBUG_DEPS + printf("-> Actually end of transaction %s:%u\n", + filename[dep->prereq->file], dep->prereq->op_num+1); +#endif + } else + /* We should never create a dependency from middle of + * a transaction. */ + assert(!in_transaction(op[prereq->file], dep->prereq.op_num) + || op[prereq->file][dep->prereq.op_num].type + == OP_TDB_TRANSACTION_COMMIT + || op[prereq->file][dep->prereq.op_num].type + == OP_TDB_TRANSACTION_CANCEL); + + list_add(&op[dep->prereq.file][dep->prereq.op_num].post, + &dep->post_list); + list_add(&op[dep->needs.file][dep->needs.op_num].pre, + &dep->pre_list); + talloc_set_destructor(dep, destroy_depend); +} + +static bool changes_db(const TDB_DATA *key, const struct op *op) +{ + return gives(key, NULL, op) != NULL; +} + +static void depend_on_previous(struct op *op[], + char *filename[], + unsigned int num, + struct op_desc user[], + unsigned int i, + int prev) +{ + bool deps[num]; + int j; + + if (i == 0) + return; + + if (prev == i - 1) { + /* Just depend on previous. */ + add_dependency(NULL, op, filename, &user[i], &user[prev]); + return; + } + + /* We have to wait for the readers. Find last one in *each* file. */ + memset(deps, 0, sizeof(deps)); + deps[user[i].file] = true; + for (j = i - 1; j > prev; j--) { + if (!deps[user[j].file]) { + add_dependency(NULL, op, filename, &user[i], &user[j]); + deps[user[j].file] = true; + } + } +} + +/* This is simple, but not complete. We don't take into account + * indirect dependencies. */ +static void optimize_dependencies(struct op *op[], unsigned int num_ops[], + unsigned int num) +{ + unsigned int i, j; + + /* There can only be one real dependency on each file */ + for (i = 0; i < num; i++) { + for (j = 1; j < num_ops[i]; j++) { + struct depend *dep, *next; + struct depend *prev[num]; + + memset(prev, 0, sizeof(prev)); + + list_for_each_safe(&op[i][j].pre, dep, next, pre_list) { + if (!prev[dep->prereq.file]) { + prev[dep->prereq.file] = dep; + continue; + } + if (prev[dep->prereq.file]->prereq.op_num + < dep->prereq.op_num) { + talloc_free(prev[dep->prereq.file]); + prev[dep->prereq.file] = dep; + } else + talloc_free(dep); + } + } + } + + for (i = 0; i < num; i++) { + int deps[num]; + + for (j = 0; j < num; j++) + deps[j] = -1; + + for (j = 1; j < num_ops[i]; j++) { + struct depend *dep, *next; + + list_for_each_safe(&op[i][j].pre, dep, next, pre_list) { + if (deps[dep->prereq.file] + >= (int)dep->prereq.op_num) + talloc_free(dep); + else + deps[dep->prereq.file] + = dep->prereq.op_num; + } + } + } +} + +#if TRAVERSALS_TAKE_TRANSACTION_LOCK +/* Force an order among the traversals, so they don't deadlock (as much) */ +static void make_traverse_depends(char *filename[], + struct op *op[], unsigned int num_ops[], + unsigned int num) +{ + unsigned int i, num_traversals = 0; + int j; + struct op_desc *desc; + + /* Sort by which one runs first. */ + int compare_traverse_desc(const void *_a, const void *_b) + { + const struct op_desc *da = _a, *db = _b; + const struct op *a = &op[da->file][da->op_num], + *b = &op[db->file][db->op_num]; + + if (a->seqnum != b->seqnum) + return a->seqnum - b->seqnum; + + /* If they have same seqnum, it means one didn't make any + * changes. Thus sort by end in that case. */ + return a[a->group_len].seqnum - b[b->group_len].seqnum; + } + + desc = talloc_array(NULL, struct op_desc, 1); + + /* Count them. */ + for (i = 0; i < num; i++) { + for (j = 1; j < num_ops[i]; j++) { + /* Traverse start (ignore those in + * transactions; they're already covered by + * transaction dependencies). */ + if (starts_traverse(&op[i][j]) + && !in_transaction(op[i], j)) { + desc = talloc_realloc(NULL, desc, + struct op_desc, + num_traversals+1); + desc[num_traversals].file = i; + desc[num_traversals].op_num = j; + num_traversals++; + } + } + } + qsort(desc, num_traversals, sizeof(desc[0]), compare_traverse_desc); + + for (i = 1; i < num_traversals; i++) { + const struct op *prev = &op[desc[i-1].file][desc[i-1].op_num]; + const struct op *curr = &op[desc[i].file][desc[i].op_num]; + + /* Read traverses don't depend on each other (read lock). */ + if (prev->type == OP_TDB_TRAVERSE_READ_START + && curr->type == OP_TDB_TRAVERSE_READ_START) + continue; + + /* Only make dependency if it's clear. */ + if (compare_traverse_desc(&desc[i], &desc[i-1])) { + /* i depends on end of traverse i-1. */ + struct op_desc end = desc[i-1]; + end.op_num += prev->group_len; + add_dependency(NULL, op, filename, &desc[i], &end); + } + } + talloc_free(desc); +} + +static void set_nonblock(int fd) +{ + if (fcntl(fd, F_SETFL, fcntl(fd, F_GETFL)|O_NONBLOCK) != 0) + err(1, "Setting pipe nonblocking"); +} + +static bool handle_backoff(struct op *op[], int fd) +{ + struct op_desc desc; + bool handled = false; + + /* Sloppy coding: we assume PIPEBUF never fills. */ + while (read(fd, &desc, sizeof(desc)) != -1) { + unsigned int i; + handled = true; + for (i = desc.op_num; i > 0; i--) { + if (op[desc.file][i].type == OP_TDB_TRAVERSE) { + /* We insert a fake end here. */ + op[desc.file][i].type + = OP_TDB_TRAVERSE_END_EARLY; + break; + } else if (starts_traverse(&op[desc.file][i])) { + unsigned int start = i; + struct op tmp = op[desc.file][i]; + /* Move the ops outside traverse. */ + memmove(&op[desc.file][i], + &op[desc.file][i+1], + (desc.op_num-i-1) * sizeof(op[0][0])); + op[desc.file][desc.op_num] = tmp; + while (op[desc.file][i].group_start == start) { + op[desc.file][i++].group_start + = desc.op_num; + } + break; + } + } + } + return handled; +} + +#else /* !TRAVERSALS_TAKE_TRANSACTION_LOCK */ +static bool handle_backoff(struct op *op[], int fd) +{ + return false; +} +#endif + +static void derive_dependencies(char *filename[], + struct op *op[], unsigned int num_ops[], + unsigned int num) +{ + struct keyinfo *hash; + unsigned int h, i; + + /* Create hash table for faster key lookup. */ + hash = hash_ops(op, num_ops, num); + + /* Sort them by sequence number. */ + sort_ops(hash, filename, op, num); + + /* Create dependencies back to the last change, rather than + * creating false dependencies by naively making each one + * depend on the previous. This has two purposes: it makes + * later optimization simpler, and it also avoids deadlock with + * same sequence number ops inside traversals (if one + * traversal doesn't write anything, two ops can have the same + * sequence number yet we can create a traversal dependency + * the other way). */ + for (h = 0; h < total_keys * 2; h++) { + int prev = -1; + + if (hash[h].num_users < 2) + continue; + + for (i = 0; i < hash[h].num_users; i++) { + if (changes_db(&hash[h].key, &op[hash[h].user[i].file] + [hash[h].user[i].op_num])) { + depend_on_previous(op, filename, num, + hash[h].user, i, prev); + prev = i; + } else if (prev >= 0) + add_dependency(hash, op, filename, + &hash[h].user[i], + &hash[h].user[prev]); + } + } + +#if TRAVERSALS_TAKE_TRANSACTION_LOCK + make_traverse_depends(filename, op, num_ops, num); +#endif + + optimize_dependencies(op, num_ops, num); +} + +static struct timeval run_test(char *argv[], + unsigned int num_ops[], + unsigned int hashsize[], + unsigned int tdb_flags[], + unsigned int open_flags[], + struct op *op[], + int fds[2]) +{ + unsigned int i; + struct timeval start, end, diff; + bool ok = true; + + for (i = 0; argv[i+2]; i++) { + struct tdb_context *tdb; + char c; + + switch (fork()) { + case -1: + err(1, "fork failed"); + case 0: + close(fds[1]); + tdb = tdb_open_ex(argv[1], hashsize[i], + tdb_flags[i]|TDB_NOSYNC, + open_flags[i], 0600, NULL, hash_key); + if (!tdb) + err(1, "Opening tdb %s", argv[1]); + + /* This catches parent exiting. */ + if (read(fds[0], &c, 1) != 1) + exit(1); + run_ops(tdb, pipes[i].fd[0], argv+2, op, i, 1, + num_ops[i], false); + check_deps(argv[2+i], op[i], num_ops[i]); + exit(0); + default: + break; + } + } + + /* Let everything settle. */ + sleep(1); + + printf("Starting run..."); + fflush(stdout); + gettimeofday(&start, NULL); + /* Tell them all to go! Any write of sufficient length will do. */ + if (write(fds[1], hashsize, i) != i) + err(1, "Writing to wakeup pipe"); + + for (i = 0; argv[i + 2]; i++) { + int status; + wait(&status); + if (!WIFEXITED(status)) { + warnx("Child died with signal %i", WTERMSIG(status)); + ok = false; + } else if (WEXITSTATUS(status) != 0) + /* Assume child spat out error. */ + ok = false; + } + if (!ok) + exit(1); + + gettimeofday(&end, NULL); + printf("done\n"); + + if (end.tv_usec < start.tv_usec) { + end.tv_usec += 1000000; + end.tv_sec--; + } + diff.tv_sec = end.tv_sec - start.tv_sec; + diff.tv_usec = end.tv_usec - start.tv_usec; + return diff; +} + +int main(int argc, char *argv[]) +{ + struct timeval diff; + unsigned int i, num_ops[argc], hashsize[argc], tdb_flags[argc], open_flags[argc]; + struct op *op[argc]; + int fds[2]; + + if (argc < 3) + errx(1, "Usage: %s ...", argv[0]); + + pipes = talloc_array(NULL, struct pipe, argc - 1); + for (i = 0; i < argc - 2; i++) { + printf("Loading tracefile %s...", argv[2+i]); + fflush(stdout); + op[i] = load_tracefile(argv[2+i], &num_ops[i], &hashsize[i], + &tdb_flags[i], &open_flags[i]); + if (pipe(pipes[i].fd) != 0) + err(1, "creating pipe"); + printf("done\n"); + } + + printf("Calculating inter-dependencies..."); + fflush(stdout); + derive_dependencies(argv+2, op, num_ops, i); + printf("done\n"); + + /* Don't fork for single arg case: simple debugging. */ + if (argc == 3) { + struct tdb_context *tdb; + tdb = tdb_open_ex(argv[1], hashsize[0], tdb_flags[0]|TDB_NOSYNC, + open_flags[0], 0600, NULL, hash_key); + printf("Single threaded run..."); + fflush(stdout); + + run_ops(tdb, pipes[0].fd[0], argv+2, op, 0, 1, num_ops[0], + false); + check_deps(argv[2], op[0], num_ops[0]); + + printf("done\n"); + exit(0); + } + + if (pipe(fds) != 0) + err(1, "creating pipe"); + +#if TRAVERSALS_TAKE_TRANSACTION_LOCK + if (pipe(pipes[argc-2].fd) != 0) + err(1, "creating pipe"); + backoff_fd = pipes[argc-2].fd[1]; + set_nonblock(pipes[argc-2].fd[1]); + set_nonblock(pipes[argc-2].fd[0]); +#endif + + do { + diff = run_test(argv, num_ops, hashsize, tdb_flags, open_flags, + op, fds); + } while (handle_backoff(op, pipes[argc-2].fd[0])); + + printf("Time replaying: %lu usec\n", + diff.tv_sec * 1000000UL + diff.tv_usec); + + exit(0); +} diff --git a/ccan/tdb/tools/tdbdump.c b/ccan/tdb/tools/tdbdump.c new file mode 100644 index 00000000..38f3de94 --- /dev/null +++ b/ccan/tdb/tools/tdbdump.c @@ -0,0 +1,120 @@ +/* + Unix SMB/CIFS implementation. + simple tdb dump util + Copyright (C) Andrew Tridgell 2001 + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . +*/ + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +static void print_data(TDB_DATA d) +{ + unsigned char *p = (unsigned char *)d.dptr; + int len = d.dsize; + while (len--) { + if (isprint(*p) && !strchr("\"\\", *p)) { + fputc(*p, stdout); + } else { + printf("\\%02X", *p); + } + p++; + } +} + +static int traverse_fn(TDB_CONTEXT *tdb, TDB_DATA key, TDB_DATA dbuf, void *state) +{ + printf("{\n"); + printf("key(%d) = \"", (int)key.dsize); + print_data(key); + printf("\"\n"); + printf("data(%d) = \"", (int)dbuf.dsize); + print_data(dbuf); + printf("\"\n"); + printf("}\n"); + return 0; +} + +static int dump_tdb(const char *fname, const char *keyname) +{ + TDB_CONTEXT *tdb; + TDB_DATA key, value; + + tdb = tdb_open(fname, 0, 0, O_RDONLY, 0); + if (!tdb) { + printf("Failed to open %s\n", fname); + return 1; + } + + if (!keyname) { + tdb_traverse(tdb, traverse_fn, NULL); + } else { + key.dptr = (void *)keyname; + key.dsize = strlen( keyname); + value = tdb_fetch(tdb, key); + if (!value.dptr) { + return 1; + } else { + print_data(value); + free(value.dptr); + } + } + + return 0; +} + +static void usage( void) +{ + printf( "Usage: tdbdump [options] \n\n"); + printf( " -h this help message\n"); + printf( " -k keyname dumps value of keyname\n"); +} + + int main(int argc, char *argv[]) +{ + char *fname, *keyname=NULL; + int c; + + if (argc < 2) { + printf("Usage: tdbdump \n"); + exit(1); + } + + while ((c = getopt( argc, argv, "hk:")) != -1) { + switch (c) { + case 'h': + usage(); + exit( 0); + case 'k': + keyname = optarg; + break; + default: + usage(); + exit( 1); + } + } + + fname = argv[optind]; + + return dump_tdb(fname, keyname); +} diff --git a/ccan/tdb/tools/tdbtorture.c b/ccan/tdb/tools/tdbtorture.c new file mode 100644 index 00000000..796fe26c --- /dev/null +++ b/ccan/tdb/tools/tdbtorture.c @@ -0,0 +1,353 @@ +/* this tests tdb by doing lots of ops from several simultaneous + writers - that stresses the locking code. +*/ + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#define REOPEN_PROB 30 +#define DELETE_PROB 8 +#define STORE_PROB 4 +#define APPEND_PROB 6 +#define TRANSACTION_PROB 10 +#define TRANSACTION_PREPARE_PROB 2 +#define LOCKSTORE_PROB 5 +#define TRAVERSE_PROB 20 +#define TRAVERSE_READ_PROB 20 +#define TRAVERSE_MOD_PROB 100 +#define TRAVERSE_ABORT_PROB 500 +#define CULL_PROB 100 +#define KEYLEN 3 +#define DATALEN 100 + +static struct tdb_context *db; +static int in_transaction; +static int in_traverse; +static int error_count; + +#ifdef PRINTF_ATTRIBUTE +static void tdb_log(struct tdb_context *tdb, enum tdb_debug_level level, const char *format, ...) PRINTF_ATTRIBUTE(3,4); +#endif +static void tdb_log(struct tdb_context *tdb, enum tdb_debug_level level, const char *format, ...) +{ + va_list ap; + + error_count++; + + va_start(ap, format); + vfprintf(stdout, format, ap); + va_end(ap); + fflush(stdout); +#if 0 + { + char *ptr; + asprintf(&ptr,"xterm -e gdb /proc/%d/exe %d", getpid(), getpid()); + system(ptr); + free(ptr); + } +#endif +} + +static void fatal(const char *why) +{ + perror(why); + error_count++; +} + +static char *randbuf(int len) +{ + char *buf; + int i; + buf = (char *)malloc(len+1); + + for (i=0;itransaction == NULL) { + TDB_LOG((tdb, TDB_DEBUG_ERROR, "tdb_transaction_cancel: no transaction\n")); + return -1; + } + + if (tdb->transaction->nesting != 0) { + tdb->transaction->transaction_error = 1; + tdb->transaction->nesting--; + return 0; + } + + tdb->map_size = tdb->transaction->old_map_size; + + /* free all the transaction blocks */ + for (i=0;itransaction->num_blocks;i++) { + if (tdb->transaction->blocks[i] != NULL) { + free(tdb->transaction->blocks[i]); + } + } + SAFE_FREE(tdb->transaction->blocks); + + /* remove any global lock created during the transaction */ + if (tdb->global_lock.count != 0) { + tdb_brlock(tdb, FREELIST_TOP, F_UNLCK, F_SETLKW, 0, 4*tdb->header.hash_size); + tdb->global_lock.count = 0; + } + + /* remove any locks created during the transaction */ + if (tdb->num_locks != 0) { + for (i=0;inum_lockrecs;i++) { + tdb_brlock(tdb,FREELIST_TOP+4*tdb->lockrecs[i].list, + F_UNLCK,F_SETLKW, 0, 1); + } + tdb->num_locks = 0; + tdb->num_lockrecs = 0; + SAFE_FREE(tdb->lockrecs); + } + + /* restore the normal io methods */ + tdb->methods = tdb->transaction->io_methods; + + tdb_brlock(tdb, FREELIST_TOP, F_UNLCK, F_SETLKW, 0, 0); + tdb_transaction_unlock(tdb); + SAFE_FREE(tdb->transaction->hash_heads); + SAFE_FREE(tdb->transaction); + + return 0; +} /* start a tdb transaction. No token is returned, as only a single @@ -414,13 +466,14 @@ int tdb_transaction_start(struct tdb_context *tdb) /* cope with nested tdb_transaction_start() calls */ if (tdb->transaction != NULL) { + tdb_trace(tdb, "tdb_transaction_start"); if (!tdb->flags & TDB_NO_NESTING) { tdb->transaction->nesting++; TDB_LOG((tdb, TDB_DEBUG_TRACE, "tdb_transaction_start: nesting %d\n", tdb->transaction->nesting)); return 0; } else { - tdb_transaction_cancel(tdb); + tdb_transaction_cancel_internal(tdb); TDB_LOG((tdb, TDB_DEBUG_TRACE, "tdb_transaction_start: cancelling previous transaction\n")); } } @@ -495,6 +548,8 @@ int tdb_transaction_start(struct tdb_context *tdb) tdb->transaction->io_methods = tdb->methods; tdb->methods = &transaction_methods; + /* Trace at the end, so we get sequence number correct. */ + tdb_trace(tdb, "tdb_transaction_start"); return 0; fail: @@ -512,57 +567,9 @@ fail: */ int tdb_transaction_cancel(struct tdb_context *tdb) { - int i; - - if (tdb->transaction == NULL) { - TDB_LOG((tdb, TDB_DEBUG_ERROR, "tdb_transaction_cancel: no transaction\n")); - return -1; - } - - if (tdb->transaction->nesting != 0) { - tdb->transaction->transaction_error = 1; - tdb->transaction->nesting--; - return 0; - } - - tdb->map_size = tdb->transaction->old_map_size; - - /* free all the transaction blocks */ - for (i=0;itransaction->num_blocks;i++) { - if (tdb->transaction->blocks[i] != NULL) { - free(tdb->transaction->blocks[i]); - } - } - SAFE_FREE(tdb->transaction->blocks); - - /* remove any global lock created during the transaction */ - if (tdb->global_lock.count != 0) { - tdb_brlock(tdb, FREELIST_TOP, F_UNLCK, F_SETLKW, 0, 4*tdb->header.hash_size); - tdb->global_lock.count = 0; - } - - /* remove any locks created during the transaction */ - if (tdb->num_locks != 0) { - for (i=0;inum_lockrecs;i++) { - tdb_brlock(tdb,FREELIST_TOP+4*tdb->lockrecs[i].list, - F_UNLCK,F_SETLKW, 0, 1); - } - tdb->num_locks = 0; - tdb->num_lockrecs = 0; - SAFE_FREE(tdb->lockrecs); - } - - /* restore the normal io methods */ - tdb->methods = tdb->transaction->io_methods; - - tdb_brlock(tdb, FREELIST_TOP, F_UNLCK, F_SETLKW, 0, 0); - tdb_transaction_unlock(tdb); - SAFE_FREE(tdb->transaction->hash_heads); - SAFE_FREE(tdb->transaction); - - return 0; + tdb_trace(tdb, "tdb_transaction_cancel"); + return tdb_transaction_cancel_internal(tdb); } - /* sync to disk */ @@ -845,6 +852,7 @@ int tdb_transaction_commit(struct tdb_context *tdb) uint32_t zero = 0; int i; + tdb_trace(tdb, "tdb_transaction_commit"); if (tdb->transaction == NULL) { TDB_LOG((tdb, TDB_DEBUG_ERROR, "tdb_transaction_commit: no transaction\n")); return -1; @@ -852,7 +860,7 @@ int tdb_transaction_commit(struct tdb_context *tdb) if (tdb->transaction->transaction_error) { tdb->ecode = TDB_ERR_IO; - tdb_transaction_cancel(tdb); + tdb_transaction_cancel_internal(tdb); TDB_LOG((tdb, TDB_DEBUG_ERROR, "tdb_transaction_commit: transaction error pending\n")); return -1; } @@ -865,7 +873,7 @@ int tdb_transaction_commit(struct tdb_context *tdb) /* check for a null transaction */ if (tdb->transaction->blocks == NULL) { - tdb_transaction_cancel(tdb); + tdb_transaction_cancel_internal(tdb); return 0; } @@ -876,7 +884,7 @@ int tdb_transaction_commit(struct tdb_context *tdb) if (tdb->num_locks || tdb->global_lock.count) { tdb->ecode = TDB_ERR_LOCK; TDB_LOG((tdb, TDB_DEBUG_ERROR, "tdb_transaction_commit: locks pending on commit\n")); - tdb_transaction_cancel(tdb); + tdb_transaction_cancel_internal(tdb); return -1; } @@ -884,7 +892,7 @@ int tdb_transaction_commit(struct tdb_context *tdb) if (tdb_brlock_upgrade(tdb, FREELIST_TOP, 0) == -1) { TDB_LOG((tdb, TDB_DEBUG_ERROR, "tdb_transaction_start: failed to upgrade hash locks\n")); tdb->ecode = TDB_ERR_LOCK; - tdb_transaction_cancel(tdb); + tdb_transaction_cancel_internal(tdb); return -1; } @@ -893,7 +901,7 @@ int tdb_transaction_commit(struct tdb_context *tdb) if (tdb_brlock(tdb, GLOBAL_LOCK, F_WRLCK, F_SETLKW, 0, 1) == -1) { TDB_LOG((tdb, TDB_DEBUG_ERROR, "tdb_transaction_commit: failed to get global lock\n")); tdb->ecode = TDB_ERR_LOCK; - tdb_transaction_cancel(tdb); + tdb_transaction_cancel_internal(tdb); return -1; } @@ -902,7 +910,7 @@ int tdb_transaction_commit(struct tdb_context *tdb) if (transaction_setup_recovery(tdb, &magic_offset) == -1) { TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_transaction_commit: failed to setup recovery data\n")); tdb_brlock(tdb, GLOBAL_LOCK, F_UNLCK, F_SETLKW, 0, 1); - tdb_transaction_cancel(tdb); + tdb_transaction_cancel_internal(tdb); return -1; } } @@ -915,7 +923,7 @@ int tdb_transaction_commit(struct tdb_context *tdb) tdb->ecode = TDB_ERR_IO; TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_transaction_commit: expansion failed\n")); tdb_brlock(tdb, GLOBAL_LOCK, F_UNLCK, F_SETLKW, 0, 1); - tdb_transaction_cancel(tdb); + tdb_transaction_cancel_internal(tdb); return -1; } tdb->map_size = tdb->transaction->old_map_size; @@ -946,7 +954,7 @@ int tdb_transaction_commit(struct tdb_context *tdb) tdb->methods = methods; tdb_transaction_recover(tdb); - tdb_transaction_cancel(tdb); + tdb_transaction_cancel_internal(tdb); tdb_brlock(tdb, GLOBAL_LOCK, F_UNLCK, F_SETLKW, 0, 1); TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_transaction_commit: write failed\n")); @@ -995,7 +1003,7 @@ int tdb_transaction_commit(struct tdb_context *tdb) /* use a transaction cancel to free memory and remove the transaction locks */ - tdb_transaction_cancel(tdb); + tdb_transaction_cancel_internal(tdb); return 0; } diff --git a/ccan/tdb/traverse.c b/ccan/tdb/traverse.c index 07b0c238..d8b15aff 100644 --- a/ccan/tdb/traverse.c +++ b/ccan/tdb/traverse.c @@ -169,6 +169,8 @@ static int tdb_traverse_internal(struct tdb_context *tdb, dbuf.dptr = key.dptr + rec.key_len; dbuf.dsize = rec.data_len; + tdb_trace_1rec_retrec(tdb, "traverse", key, dbuf); + /* Drop chain lock, call out */ if (tdb_unlock(tdb, tl->hash, tl->lock_rw) != 0) { ret = -1; @@ -177,6 +179,7 @@ static int tdb_traverse_internal(struct tdb_context *tdb, } if (fn && fn(tdb, key, dbuf, private_data)) { /* They want us to terminate traversal */ + tdb_trace_ret(tdb, "tdb_traverse_end", count); ret = count; if (tdb_unlock_record(tdb, tl->off) != 0) { TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_traverse: unlock_record failed!\n"));; @@ -187,6 +190,7 @@ static int tdb_traverse_internal(struct tdb_context *tdb, } SAFE_FREE(key.dptr); } + tdb_trace(tdb, "tdb_traverse_end"); out: tdb->travlocks.next = tl->next; if (ret < 0) @@ -212,6 +216,7 @@ int tdb_traverse_read(struct tdb_context *tdb, } tdb->traverse_read++; + tdb_trace(tdb, "tdb_traverse_read_start"); ret = tdb_traverse_internal(tdb, fn, private_data, &tl); tdb->traverse_read--; @@ -236,12 +241,13 @@ int tdb_traverse(struct tdb_context *tdb, if (tdb->read_only || tdb->traverse_read) { return tdb_traverse_read(tdb, fn, private_data); } - + if (tdb_transaction_lock(tdb, F_WRLCK)) { return -1; } tdb->traverse_write++; + tdb_trace(tdb, "tdb_traverse_start"); ret = tdb_traverse_internal(tdb, fn, private_data, &tl); tdb->traverse_write--; @@ -264,12 +270,16 @@ TDB_DATA tdb_firstkey(struct tdb_context *tdb) tdb->travlocks.lock_rw = F_RDLCK; /* Grab first record: locks chain and returned record. */ - if (tdb_next_lock(tdb, &tdb->travlocks, &rec) <= 0) + if (tdb_next_lock(tdb, &tdb->travlocks, &rec) <= 0) { + tdb_trace_retrec(tdb, "tdb_firstkey", tdb_null); return tdb_null; + } /* now read the key */ key.dsize = rec.key_len; key.dptr =tdb_alloc_read(tdb,tdb->travlocks.off+sizeof(rec),key.dsize); + tdb_trace_retrec(tdb, "tdb_firstkey", key); + /* Unlock the hash chain of the record we just read. */ if (tdb_unlock(tdb, tdb->travlocks.hash, tdb->travlocks.lock_rw) != 0) TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_firstkey: error occurred while tdb_unlocking!\n")); @@ -294,6 +304,8 @@ TDB_DATA tdb_nextkey(struct tdb_context *tdb, TDB_DATA oldkey) || memcmp(k, oldkey.dptr, oldkey.dsize) != 0) { /* No, it wasn't: unlock it and start from scratch */ if (tdb_unlock_record(tdb, tdb->travlocks.off) != 0) { + tdb_trace_1rec_retrec(tdb, "tdb_nextkey", + oldkey, tdb_null); SAFE_FREE(k); return tdb_null; } @@ -310,8 +322,10 @@ TDB_DATA tdb_nextkey(struct tdb_context *tdb, TDB_DATA oldkey) if (!tdb->travlocks.off) { /* No previous element: do normal find, and lock record */ tdb->travlocks.off = tdb_find_lock_hash(tdb, oldkey, tdb->hash_fn(&oldkey), tdb->travlocks.lock_rw, &rec); - if (!tdb->travlocks.off) + if (!tdb->travlocks.off) { + tdb_trace_1rec_retrec(tdb, "tdb_nextkey", oldkey, tdb_null); return tdb_null; + } tdb->travlocks.hash = BUCKET(rec.full_hash); if (tdb_lock_record(tdb, tdb->travlocks.off) != 0) { TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_nextkey: lock_record failed (%s)!\n", strerror(errno))); @@ -333,6 +347,7 @@ TDB_DATA tdb_nextkey(struct tdb_context *tdb, TDB_DATA oldkey) /* Unlock the chain of old record */ if (tdb_unlock(tdb, BUCKET(oldhash), tdb->travlocks.lock_rw) != 0) TDB_LOG((tdb, TDB_DEBUG_FATAL, "tdb_nextkey: WARNING tdb_unlock failed!\n")); + tdb_trace_1rec_retrec(tdb, "tdb_nextkey", oldkey, key); return key; } diff --git a/junkcode/fork0@users.sf.net-bitmaps/bitmaps.h b/junkcode/fork0@users.sf.net-bitmaps/bitmaps.h new file mode 100644 index 00000000..05ecd962 --- /dev/null +++ b/junkcode/fork0@users.sf.net-bitmaps/bitmaps.h @@ -0,0 +1,78 @@ +/* bitmaps and bitmap operations */ +#ifndef _BITMAPS_H_ +#define _BITMAPS_H_ + +/* + * Bitmaps are arrays of unsigned ints, filled with bits in most- + * significant-first order. So bitmap[0] shall contain the bits from + * 0 to 31 on a 32bit architecture, bitmap[1] - 32-63, and so forth. + * + * The callers are responsible to do all the bounds-checking. + */ +enum { BITS_PER_BITMAP_ELEM = 8 * sizeof(unsigned) }; + +typedef unsigned bitmap_elem_t; + +/* returned is the unshifted bit state. IOW: NOT 0 or 1, but something + * like 0x00001000 or 0x40000000 */ +static inline +bitmap_elem_t bitmap_test_bit(const bitmap_elem_t* bits, unsigned bit) +{ + if ( sizeof(*bits) == 4 ) + return bits[bit >> 5] & (0x80000000 >> (bit & 0x1f)); + else if ( sizeof(*bits) == 8 ) + return bits[bit >> 6] & (0x8000000000000000ull >> (bit & 0x3f)); + else + { + return bits[bit / BITS_PER_BITMAP_ELEM] & + 1 << ((BITS_PER_BITMAP_ELEM - bit % BITS_PER_BITMAP_ELEM) - 1); + } +} + +static inline +bitmap_elem_t bitmap_set_bit(bitmap_elem_t* bits, unsigned bit) +{ + if ( sizeof(*bits) == 4 ) + return bits[bit >> 5] |= (0x80000000 >> (bit & 0x1f)); + else if ( sizeof(*bits) == 8 ) + return bits[bit >> 6] |= (0x8000000000000000ull >> (bit & 0x3f)); + else + { + return bits[bit / BITS_PER_BITMAP_ELEM] |= + 1 << ((BITS_PER_BITMAP_ELEM - bit % BITS_PER_BITMAP_ELEM) - 1); + } +} + +/* pos must position the bits inside of a bitmap element, otherwise + * the index shift puts the bits in the wrong word (for simplicity). + * Only low 8 bits of b8 shall be used */ +static inline +void bitmap_set_8bits_fast(bitmap_elem_t* bits, unsigned pos, unsigned b8) +{ + if ( sizeof(*bits) == 4 ) + bits[pos >> 5] |= b8 << (24 - (pos & 0x1f)); + else if ( sizeof(*bits) == 8 ) + bits[pos >> 6] |= b8 << (56 - (pos & 0x3f)); + else + { + bits[pos / BITS_PER_BITMAP_ELEM] |= + b8 << (BITS_PER_BITMAP_ELEM - 8 - pos % BITS_PER_BITMAP_ELEM); + } +} + +static inline +bitmap_elem_t bitmap_clear_bit(bitmap_elem_t* bits, unsigned bit) +{ + if ( sizeof(*bits) == 4 ) + return bits[bit >> 5] &= ~(0x80000000 >> (bit & 0x1f)); + else if ( sizeof(*bits) == 8 ) + return bits[bit >> 6] &= ~(0x8000000000000000ull >> (bit & 0x3f)); + else + { + return bits[bit / BITS_PER_BITMAP_ELEM] &= + ~(1 << ((BITS_PER_BITMAP_ELEM - bit % BITS_PER_BITMAP_ELEM) - 1)); + } +} + +#endif /* _BITMAPS_H_ */ + diff --git a/junkcode/fork0@users.sf.net-pathexpand/pathexpand.c b/junkcode/fork0@users.sf.net-pathexpand/pathexpand.c new file mode 100644 index 00000000..4b8bcf0f --- /dev/null +++ b/junkcode/fork0@users.sf.net-pathexpand/pathexpand.c @@ -0,0 +1,96 @@ +#include +#include +#include + +/* + * Returns the analog of "cd path" from a directory "cwd". + * The root is defined as empty path (instead of "/") + * An attempt to go past the root (with "..") leaves the path at root. + * The cwd is not expanded. + */ +char *pathexpand(const char *cwd, const char *path) +{ + static const char SEP[] = "/"; + if (!*path) /* empty path -> "." (don't move) */ + path = "."; + if (!*cwd || *SEP == *path) /* no cwd, or path begins with "/" */ + cwd = ""; + + while (*cwd && *SEP == *cwd) + ++cwd; + + size_t len = strlen(cwd); + char *out = malloc(len + 1 + strlen(path) + 1); + char *p = strcpy(out, cwd) + len; + + for (; *path; ++path) + { + char *pl; + if (p > out && p[-1] != *SEP) + *p++ = *SEP; + pl = p; + while (*path && *SEP != *path) + *p++ = *path++; + *p = '\0'; + /* ..."//"... */ + if (p == pl) + ; /* just ignore */ + /* ..."/./"... */ + else if ( p - pl == 1 && '.' == *pl ) + --p; /* just ignore */ + /* ..."/../"... */ + else if ( p - pl == 2 && '.' == pl[0] && '.' == pl[1] ) + { + /* drop the last element of the resulting path */ + if (pl > out && --pl > out) + for (--pl; pl > out && *SEP != *pl; --pl) + ; + p = pl > out ? ++pl: out; + } + /* ..."/path/"... */ + else if (*path) + *p++ = *path; /* just add the separator */ + + if (!*path) + break; + } + if (p > out+1 && *SEP == p[-1]) + --p; + *p = '\0'; + return out; +} + +#ifdef CHECK_PATHEXPAND +static void check(const char *cwd, const char *path, const char *good) +{ + static int n = 0; + printf("%-2d: %10s$ cd %s", ++n, cwd, path); + char *t = pathexpand(cwd, path); + if ( strcmp(t, good) ) + printf(" ____________________failed(%s)\n", t); + else + printf(" \033[32m%s\033[0m\n", t); + free(t); +} + +int main(int argc, char **argv) +{ + /* 1 */ check("/onelevel", "aa", "onelevel/aa"); + /* 2 */ check("/", "..", ""); + /* 3 */ check("/", "../..", ""); + /* 4 */ check("/one", "aa/../bb", "one/bb"); + /* 5 */ check("/one/two", "aa//bb", "one/two/aa/bb"); + /* 6 */ check("", "/aa//bb", "aa/bb"); + /* 7 */ check("/one/two", "", "one/two"); + /* 8 */ check("/one/two", "aa/..bb/x/../cc/", "one/two/aa/..bb/cc"); + /* 9 */ check("/one/two", "aa/x/././cc////", "one/two/aa/x/cc"); + /* 10 */ check("/one/two", "../../../../aa", "aa"); + /* 11 */ check("one/", "../one/two", "one/two"); + /* 12 */ check("", "../../two", "two"); + /* 13 */ check("a/b/c", "../../two", "a/two"); + /* 14 */ check("a/b/", "../two", "a/two"); + /* 15 */ check("///", "../two", "two"); + return 0; +} +#endif + diff --git a/junkcode/fork0@users.sf.net-timeout/timeout.c b/junkcode/fork0@users.sf.net-timeout/timeout.c new file mode 100644 index 00000000..290e4276 --- /dev/null +++ b/junkcode/fork0@users.sf.net-timeout/timeout.c @@ -0,0 +1,173 @@ +/* execute a program with a timeout by alarm(2) */ +#define _GNU_SOURCE +#include +#include +#include +#include +#include +#include +#include +#include + +static const char *argv0; +static char **prgargv; +static pid_t pid; +static int signo; +static unsigned int timeout; + +static void timedout(int sig) +{ + fprintf(stderr, "%s[%d]: %s[%d] timed out after %u sec\n", + argv0, getpid(), *prgargv, pid, timeout); + if (pid) + kill(-pid, signo); +} + +static void interrupted(int sig) +{ + alarm(0); + if (pid) + kill(-pid, sig); +} + +static void usage() +{ + fprintf(stderr, "%s [-] program ...\n" + "Where is a signal number (see kill -l).\n" + "Some symbolic names recognized. KILL used by default\n", + argv0); + exit(1); +} + +static struct { + const char *name; + int signo; +} known[] = { + {"HUP", SIGHUP}, + {"INT", SIGINT}, + {"QUIT", SIGQUIT}, + {"ILL", SIGILL}, + {"TRAP", SIGTRAP}, + {"ABRT", SIGABRT}, + {"BUS", SIGBUS}, + {"FPE", SIGFPE}, + {"KILL", SIGKILL}, + {"USR1", SIGUSR1}, + {"SEGV", SIGSEGV}, + {"USR2", SIGUSR2}, + {"PIPE", SIGPIPE}, + {"ALRM", SIGALRM}, + {"TERM", SIGTERM}, + {"STKFLT", SIGSTKFLT}, + {"CHLD", SIGCHLD}, + {"CONT", SIGCONT}, + {"STOP", SIGSTOP}, + {"TSTP", SIGTSTP}, + {"TTIN", SIGTTIN}, + {"TTOU", SIGTTOU}, + {"URG", SIGURG}, + {"XCPU", SIGXCPU}, + {"XFSZ", SIGXFSZ}, + {"VTALRM", SIGVTALRM}, + {"PROF", SIGPROF}, + {"WINCH", SIGWINCH}, + {"IO", SIGIO}, + {"PWR", SIGPWR}, + {"SYS", SIGSYS}, +}; + +static int signo_arg(const char *arg) +{ + if (*arg == '-') { + char *p; + int s = strtol(++arg, &p, 10); + if (!*p && p > arg && s > 0 && s < _NSIG) { + signo = s; + return 1; + } + if (!strncasecmp(arg, "SIG", 3)) + arg += 3; + for (s = 0; s < sizeof(known)/sizeof(*known); ++s) + if (!strcasecmp(arg, known[s].name)) { + signo = known[s].signo; + return 1; + } + } + return 0; +} + +int main(int argc, char** argv) +{ + argv0 = strrchr(*argv, '/'); + if (argv0) + ++argv0; + else + argv0 = *argv; + + signal(SIGALRM, timedout); + signal(SIGINT, interrupted); + signal(SIGHUP, interrupted); + + ++argv; + + if (!*argv) + usage(); + + if (signo_arg(*argv)) + ++argv; + if (sscanf(*argv, "%u", &timeout) == 1) + ++argv; + else + usage(); + if (!signo && signo_arg(*argv)) + ++argv; + if (!signo) + signo = SIGKILL; + + if (!*argv) + usage(); + + prgargv = argv; + alarm(timeout); + pid = fork(); + + if (!pid) { + signal(SIGALRM, SIG_DFL); + signal(SIGCHLD, SIG_DFL); + signal(SIGINT, SIG_DFL); + signal(SIGHUP, SIG_DFL); + setpgid(0, 0); + execvp(*prgargv, prgargv); + fprintf(stderr, "%s: %s: %s\n", + argv0, *prgargv, strerror(errno)); + _exit(2); + } else if (pid < 0) { + fprintf(stderr, "%s: %s\n", argv0, strerror(errno)); + } else { + int status; + while (waitpid(pid, &status, 0) < 0 && EINTR == errno) + ; + alarm(0); + if (WIFEXITED(status)) + return WEXITSTATUS(status); + if (WIFSIGNALED(status)) { + /* + * Some signals are special, lets die with + * the same signal as child process + */ + if (WTERMSIG(status) == SIGHUP || + WTERMSIG(status) == SIGINT || + WTERMSIG(status) == SIGTERM || + WTERMSIG(status) == SIGQUIT || + WTERMSIG(status) == SIGKILL) { + signal(WTERMSIG(status), SIG_DFL); + raise(WTERMSIG(status)); + } + fprintf(stderr, "%s: %s: %s\n", + argv0, *prgargv, strsignal(WTERMSIG(status))); + } + else + fprintf(stderr, "%s died\n", *prgargv); + } + return 2; +}