[PATCH] Switch from random to sequential thread identifiers.

[PATCH] Switch from random to sequential thread identifiers.

[Carl Worth]

The sequential identifiers have the advantage of being guaranteed to
be unique (until we overflow a 64-bit unsigned integer), and also take
up slightly less space in the "notmuch search" output (20 columns
rather than 32).

This change also has the side effect of fixing a bug where notmuch
could block on /dev/random at startup (waiting for some entropy to
appear). This bug was hit hard by the test suite, (which could easily
exhaust the available entropy on common systems---resulting in large
delays of the test suite).

---

I'm sending this patch to the mailing-list rather than pushing it
directly so that any authors of user interfaces can ensure that they are
ready for the length of thread identifiers in "notmuch search" output to
change.

I tested that the emacs client doesn't need any change in this regard.

And the change doesn't introduce any compatibility with an existing
database, so no rebuild required (hurrah!).

-Carl

 lib/database-private.h |    7 +++++-
 lib/database.cc        |   52 ++++++++++++++++++++++++++++++++++++++++++++---
 lib/message.cc         |   46 ------------------------------------------
 test/notmuch-test      |    2 +-
 4 files changed, 55 insertions(+), 52 deletions(-)

diff --git a/lib/database-private.h b/lib/database-private.h
index 5891584..5bb6e86 100644
--- a/lib/database-private.h
+++ b/lib/database-private.h
@@ -27,14 +27,19 @@
 
 struct _notmuch_database {
     notmuch_bool_t exception_reported;
+
     char *path;
+
+    notmuch_bool_t needs_upgrade;
     notmuch_database_mode_t mode;
     Xapian::Database *xapian_db;
+
+    uint64_t last_thread_id;
+
     Xapian::QueryParser *query_parser;
     Xapian::TermGenerator *term_gen;
     Xapian::ValueRangeProcessor *value_range_processor;
 
-    notmuch_bool_t needs_upgrade;
 };
 
 /* Convert tags from Xapian internal format to notmuch format.
diff --git a/lib/database.cc b/lib/database.cc
index cce7847..65ff12e 100644
--- a/lib/database.cc
+++ b/lib/database.cc
@@ -533,6 +533,8 @@ notmuch_database_open (const char *path,
     notmuch->needs_upgrade = FALSE;
     notmuch->mode = mode;
     try {
+	string last_thread_id;
+
 	if (mode == NOTMUCH_DATABASE_MODE_READ_WRITE) {
 	    notmuch->xapian_db = new Xapian::WritableDatabase (xapian_path,
 							       Xapian::DB_CREATE_OR_OPEN);
@@ -567,6 +569,20 @@ notmuch_database_open (const char *path,
 			 notmuch_path, version, NOTMUCH_DATABASE_VERSION);
 	    }
 	}
+
+	last_thread_id = notmuch->xapian_db->get_metadata ("last_thread_id");
+	if (last_thread_id.empty ()) {
+	    notmuch->last_thread_id = 0;
+	} else {
+	    const char *str;
+	    char *end;
+
+	    str = last_thread_id.c_str ();
+	    notmuch->last_thread_id = strtoull (str, &end, 10);
+	    if (*end != '\0')
+		INTERNAL_ERROR ("Malformed database last_thread_id: %s", str);
+	}
+
 	notmuch->query_parser = new Xapian::QueryParser;
 	notmuch->term_gen = new Xapian::TermGenerator;
 	notmuch->term_gen->set_stemmer (Xapian::Stem ("english"));
@@ -1278,14 +1294,38 @@ _notmuch_database_link_message_to_children (notmuch_database_t *notmuch,
     return ret;
 }
 
+static const char *
+_notmuch_database_generate_thread_id (notmuch_database_t *notmuch)
+{
+    /* 20 bytes (+ terminator) for ASCII decimal representation of
+     * a 64-bit integer. */
+    static char thread_id[21];
+    Xapian::WritableDatabase *db;
+
+    db = static_cast <Xapian::WritableDatabase *> (notmuch->xapian_db);
+
+    notmuch->last_thread_id++;
+
+    sprintf (thread_id, "%020llu", notmuch->last_thread_id);
+
+    db->set_metadata ("last_thread_id", thread_id);
+
+    return thread_id;
+}
+
 /* Given a (mostly empty) 'message' and its corresponding
  * 'message_file' link it to existing threads in the database.
  *
  * We first look at 'message_file' and its link-relevant headers
  * (References and In-Reply-To) for message IDs. We also look in the
- * database for existing message that reference 'message'.
+ * database for existing message that reference 'message'. In either
+ * case, we will assign to the current message the first thread_id
+ * found (through either parent or child). We will also merge any
+ * existing, distinct threads where this message belongs to both,
+ * (which is not uncommon when mesages are processed out of order).
  *
- * The end result is to call _notmuch_message_ensure_thread_id which
+ * Finally, if not thread ID has been found through parent or child,
+ * we call _notmuch_message_generate_thread_id to generate a new
  * generates a new thread ID if the message doesn't connect to any
  * existing threads.
  */
@@ -1308,8 +1348,12 @@ _notmuch_database_link_message (notmuch_database_t *notmuch,
     if (status)
 	return status;
 
-    if (thread_id == NULL)
-	_notmuch_message_ensure_thread_id (message);
+    /* If not part of any existing thread, generate a new thread ID. */
+    if (thread_id == NULL) {
+	thread_id = _notmuch_database_generate_thread_id (notmuch);
+
+	_notmuch_message_add_term (message, "thread", thread_id);
+    }
 
     return NOTMUCH_STATUS_SUCCESS;
 }
diff --git a/lib/message.cc b/lib/message.cc
index f0e905b..0195050 100644
--- a/lib/message.cc
+++ b/lib/message.cc
@@ -42,13 +42,6 @@ struct _notmuch_message {
     Xapian::Document doc;
 };
 
-/* "128 bits of thread-id ought to be enough for anybody" */
-#define NOTMUCH_THREAD_ID_BITS	 128
-#define NOTMUCH_THREAD_ID_DIGITS (NOTMUCH_THREAD_ID_BITS / 4)
-typedef struct _thread_id {
-    char str[NOTMUCH_THREAD_ID_DIGITS + 1];
-} thread_id_t;
-
 /* We end up having to call the destructor explicitly because we had
  * to use "placement new" in order to initialize C++ objects within a
  * block that we allocated with talloc. So C++ is making talloc
@@ -557,45 +550,6 @@ _notmuch_message_set_date (notmuch_message_t *message,
 			    Xapian::sortable_serialise (time_value));
 }
 
-static void
-thread_id_generate (thread_id_t *thread_id)
-{
-    static int seeded = 0;
-    FILE *dev_random;
-    uint32_t value;
-    char *s;
-    int i;
-
-    if (! seeded) {
-	dev_random = fopen ("/dev/random", "r");
-	if (dev_random == NULL) {
-	    srand (time (NULL));
-	} else {
-	    fread ((void *) &value, sizeof (value), 1, dev_random);
-	    srand (value);
-	    fclose (dev_random);
-	}
-	seeded = 1;
-    }
-
-    s = thread_id->str;
-    for (i = 0; i < NOTMUCH_THREAD_ID_DIGITS; i += 8) {
-	value = rand ();
-	sprintf (s, "%08x", value);
-	s += 8;
-    }
-}
-
-void
-_notmuch_message_ensure_thread_id (notmuch_message_t *message)
-{
-    /* If not part of any existing thread, generate a new thread_id. */
-    thread_id_t thread_id;
-
-    thread_id_generate (&thread_id);
-    _notmuch_message_add_term (message, "thread", thread_id.str);
-}
-
 /* Synchronize changes made to message->doc out into the database. */
 void
 _notmuch_message_sync (notmuch_message_t *message)
diff --git a/test/notmuch-test b/test/notmuch-test
index 2e5eb24..cac5705 100755
--- a/test/notmuch-test
+++ b/test/notmuch-test
@@ -146,7 +146,7 @@ add_message ()
 }
 
 NOTMUCH_IGNORED_OUTPUT_REGEXP='^Processed [0-9]*( total)? file|Found [0-9]* total file'
-NOTMUCH_THREAD_ID_SQUELCH='s/thread:................................/thread:XXX/'
+NOTMUCH_THREAD_ID_SQUELCH='s/thread:..................../thread:XXX/'
 execute_expecting ()
 {
     args=$1
-- 
1.6.5.7

Re: [PATCH] Switch from random to sequential thread identifiers.

[Carl Worth]

The sequential identifiers have the advantage of being guaranteed to
be unique (until we overflow a 64-bit unsigned integer), and also take
up half as much space in the "notmuch search" output (16 columns
rather than 32).

This change also has the side effect of fixing a bug where notmuch
could block on /dev/random at startup (waiting for some entropy to
appear). This bug was hit hard by the test suite, (which could easily
exhaust the available entropy on common systems---resulting in large
delays of the test suite).
---

Keith pointed out to me that there was obviously no benefit from
switching from hexadecimal to decimal here. So this second version of
the patch means 16-character identifiers rather than 20.

 lib/database-private.h |    7 +++++-
 lib/database.cc        |   52 ++++++++++++++++++++++++++++++++++++++++++++---
 lib/message.cc         |   46 ------------------------------------------
 test/notmuch-test      |    2 +-
 4 files changed, 55 insertions(+), 52 deletions(-)

diff --git a/lib/database-private.h b/lib/database-private.h
index 5891584..5bb6e86 100644
--- a/lib/database-private.h
+++ b/lib/database-private.h
@@ -27,14 +27,19 @@
 
 struct _notmuch_database {
     notmuch_bool_t exception_reported;
+
     char *path;
+
+    notmuch_bool_t needs_upgrade;
     notmuch_database_mode_t mode;
     Xapian::Database *xapian_db;
+
+    uint64_t last_thread_id;
+
     Xapian::QueryParser *query_parser;
     Xapian::TermGenerator *term_gen;
     Xapian::ValueRangeProcessor *value_range_processor;
 
-    notmuch_bool_t needs_upgrade;
 };
 
 /* Convert tags from Xapian internal format to notmuch format.
diff --git a/lib/database.cc b/lib/database.cc
index cce7847..8641321 100644
--- a/lib/database.cc
+++ b/lib/database.cc
@@ -533,6 +533,8 @@ notmuch_database_open (const char *path,
     notmuch->needs_upgrade = FALSE;
     notmuch->mode = mode;
     try {
+	string last_thread_id;
+
 	if (mode == NOTMUCH_DATABASE_MODE_READ_WRITE) {
 	    notmuch->xapian_db = new Xapian::WritableDatabase (xapian_path,
 							       Xapian::DB_CREATE_OR_OPEN);
@@ -567,6 +569,20 @@ notmuch_database_open (const char *path,
 			 notmuch_path, version, NOTMUCH_DATABASE_VERSION);
 	    }
 	}
+
+	last_thread_id = notmuch->xapian_db->get_metadata ("last_thread_id");
+	if (last_thread_id.empty ()) {
+	    notmuch->last_thread_id = 0;
+	} else {
+	    const char *str;
+	    char *end;
+
+	    str = last_thread_id.c_str ();
+	    notmuch->last_thread_id = strtoull (str, &end, 16);
+	    if (*end != '\0')
+		INTERNAL_ERROR ("Malformed database last_thread_id: %s", str);
+	}
+
 	notmuch->query_parser = new Xapian::QueryParser;
 	notmuch->term_gen = new Xapian::TermGenerator;
 	notmuch->term_gen->set_stemmer (Xapian::Stem ("english"));
@@ -1278,14 +1294,38 @@ _notmuch_database_link_message_to_children (notmuch_database_t *notmuch,
     return ret;
 }
 
+static const char *
+_notmuch_database_generate_thread_id (notmuch_database_t *notmuch)
+{
+    /* 16 bytes (+ terminator) for hexadecimal representation of
+     * a 64-bit integer. */
+    static char thread_id[17];
+    Xapian::WritableDatabase *db;
+
+    db = static_cast <Xapian::WritableDatabase *> (notmuch->xapian_db);
+
+    notmuch->last_thread_id++;
+
+    sprintf (thread_id, "%016llx", notmuch->last_thread_id);
+
+    db->set_metadata ("last_thread_id", thread_id);
+
+    return thread_id;
+}
+
 /* Given a (mostly empty) 'message' and its corresponding
  * 'message_file' link it to existing threads in the database.
  *
  * We first look at 'message_file' and its link-relevant headers
  * (References and In-Reply-To) for message IDs. We also look in the
- * database for existing message that reference 'message'.
+ * database for existing message that reference 'message'. In either
+ * case, we will assign to the current message the first thread_id
+ * found (through either parent or child). We will also merge any
+ * existing, distinct threads where this message belongs to both,
+ * (which is not uncommon when mesages are processed out of order).
  *
- * The end result is to call _notmuch_message_ensure_thread_id which
+ * Finally, if not thread ID has been found through parent or child,
+ * we call _notmuch_message_generate_thread_id to generate a new
  * generates a new thread ID if the message doesn't connect to any
  * existing threads.
  */
@@ -1308,8 +1348,12 @@ _notmuch_database_link_message (notmuch_database_t *notmuch,
     if (status)
 	return status;
 
-    if (thread_id == NULL)
-	_notmuch_message_ensure_thread_id (message);
+    /* If not part of any existing thread, generate a new thread ID. */
+    if (thread_id == NULL) {
+	thread_id = _notmuch_database_generate_thread_id (notmuch);
+
+	_notmuch_message_add_term (message, "thread", thread_id);
+    }
 
     return NOTMUCH_STATUS_SUCCESS;
 }
diff --git a/lib/message.cc b/lib/message.cc
index f0e905b..0195050 100644
--- a/lib/message.cc
+++ b/lib/message.cc
@@ -42,13 +42,6 @@ struct _notmuch_message {
     Xapian::Document doc;
 };
 
-/* "128 bits of thread-id ought to be enough for anybody" */
-#define NOTMUCH_THREAD_ID_BITS	 128
-#define NOTMUCH_THREAD_ID_DIGITS (NOTMUCH_THREAD_ID_BITS / 4)
-typedef struct _thread_id {
-    char str[NOTMUCH_THREAD_ID_DIGITS + 1];
-} thread_id_t;
-
 /* We end up having to call the destructor explicitly because we had
  * to use "placement new" in order to initialize C++ objects within a
  * block that we allocated with talloc. So C++ is making talloc
@@ -557,45 +550,6 @@ _notmuch_message_set_date (notmuch_message_t *message,
 			    Xapian::sortable_serialise (time_value));
 }
 
-static void
-thread_id_generate (thread_id_t *thread_id)
-{
-    static int seeded = 0;
-    FILE *dev_random;
-    uint32_t value;
-    char *s;
-    int i;
-
-    if (! seeded) {
-	dev_random = fopen ("/dev/random", "r");
-	if (dev_random == NULL) {
-	    srand (time (NULL));
-	} else {
-	    fread ((void *) &value, sizeof (value), 1, dev_random);
-	    srand (value);
-	    fclose (dev_random);
-	}
-	seeded = 1;
-    }
-
-    s = thread_id->str;
-    for (i = 0; i < NOTMUCH_THREAD_ID_DIGITS; i += 8) {
-	value = rand ();
-	sprintf (s, "%08x", value);
-	s += 8;
-    }
-}
-
-void
-_notmuch_message_ensure_thread_id (notmuch_message_t *message)
-{
-    /* If not part of any existing thread, generate a new thread_id. */
-    thread_id_t thread_id;
-
-    thread_id_generate (&thread_id);
-    _notmuch_message_add_term (message, "thread", thread_id.str);
-}
-
 /* Synchronize changes made to message->doc out into the database. */
 void
 _notmuch_message_sync (notmuch_message_t *message)
diff --git a/test/notmuch-test b/test/notmuch-test
index 2e5eb24..cac5705 100755
--- a/test/notmuch-test
+++ b/test/notmuch-test
@@ -146,7 +146,7 @@ add_message ()
 }
 
 NOTMUCH_IGNORED_OUTPUT_REGEXP='^Processed [0-9]*( total)? file|Found [0-9]* total file'
-NOTMUCH_THREAD_ID_SQUELCH='s/thread:................................/thread:XXX/'
+NOTMUCH_THREAD_ID_SQUELCH='s/thread:..................../thread:XXX/'
 execute_expecting ()
 {
     args=$1
-- 
1.6.5.7

Re: [PATCH] Switch from random to sequential thread identifiers.

[Sebastian Spaeth]

On Mon, 08 Feb 2010 13:36:14 -0800, Carl Worth <cworth@cworth.org> wrote:
> diff --git a/lib/database-private.h b/lib/database-private.h
...
> +
> +    uint64_t last_thread_id;

throws:
lib/database-private.h:37: error: 'uint64_t' does not name a type


Is it just me, or have I made an error in applying this patch?

spaetz

Re: [PATCH] Switch from random to sequential thread identifiers.

[Sebastian Spaeth]

On Tue, 09 Feb 2010 10:58:53 +0100, Sebastian Spaeth <Sebastian@SSpaeth.de> wrote:
> On Mon, 08 Feb 2010 13:36:14 -0800, Carl Worth <cworth@cworth.org> wrote:
> > diff --git a/lib/database-private.h b/lib/database-private.h
> ...
> > +
> > +    uint64_t last_thread_id;
> 
> throws:
> lib/database-private.h:37: error: 'uint64_t' does not name a type

using "unsigned long long int" works fine though. I think gcc 4.4 does
not include stdint by default anymore in C++ or something...

Re: [PATCH] Switch from random to sequential thread identifiers.

[Sebastian Spaeth]

On Mon, 08 Feb 2010 13:36:14 -0800, Carl Worth <cworth@cworth.org> wrote:
> -NOTMUCH_THREAD_ID_SQUELCH='s/thread:................................/thread:XXX/'
> +NOTMUCH_THREAD_ID_SQUELCH='s/thread:..................../thread:XXX/'

Caught you not running your test suite before submitting v2 of a patch!
:-)

This still assumes the 20 digit thread ids.

Sebastian

Re: [PATCH] Switch from random to sequential thread identifiers.

[Michal Sojka]

On Mon, 08 Feb 2010 13:36:14 -0800, Carl Worth <cworth@cworth.org> wrote:
> The sequential identifiers have the advantage of being guaranteed to
> be unique (until we overflow a 64-bit unsigned integer), and also take
> up half as much space in the "notmuch search" output (16 columns
> rather than 32).
>  [...]

On amd64 I get:
lib/database.cc: In function ‘const char* _notmuch_database_generate_thread_id(notmuch_database_t*)’:
lib/database.cc:1309: warning: format ‘%016llx’ expects type ‘long long unsigned int’, but argument 3 has type ‘uint64_t’

What about the following? This could also fix Sebastian's problem.

---- 8< ----
From afcc07ae03ae40cf7e1c33d8632fba0a9fc0b4c8 Mon Sep 17 00:00:00 2001
From: Michal Sojka <sojkam1@fel.cvut.cz>
Date: Tue, 9 Feb 2010 15:35:39 +0100
Subject: [PATCH] Suppress warning on amd64

---
 lib/database.cc |    5 ++++-
 1 files changed, 4 insertions(+), 1 deletions(-)

diff --git a/lib/database.cc b/lib/database.cc
index 8641321..20a4c72 100644
--- a/lib/database.cc
+++ b/lib/database.cc
@@ -26,6 +26,9 @@
 #include <signal.h>
 #include <xapian.h>

+#define __STDC_FORMAT_MACROS
+#include <inttypes.h>
+
 #include <glib.h> /* g_free, GPtrArray, GHashTable */

 using namespace std;
@@ -1306,7 +1309,7 @@ _notmuch_database_generate_thread_id (notmuch_database_t *notmuch)

     notmuch->last_thread_id++;

-    sprintf (thread_id, "%016llx", notmuch->last_thread_id);
+    sprintf (thread_id, "%016"PRIx64, notmuch->last_thread_id);

     db->set_metadata ("last_thread_id", thread_id);

Re: [PATCH] Switch from random to sequential thread identifiers.

[Carl Worth]

[-- Attachment #1: Type: text/plain, Size: 1096 bytes --]

On Tue, 09 Feb 2010 15:40:00 +0100, Michal Sojka <sojkam1@fel.cvut.cz> wrote:
> What about the following? This could also fix Sebastian's problem.
...
> +#define __STDC_FORMAT_MACROS
> +#include <inttypes.h>
...
> -    sprintf (thread_id, "%016llx", notmuch->last_thread_id);
> +    sprintf (thread_id, "%016"PRIx64, notmuch->last_thread_id);

Excellent! I did hesitate for a moment when typing "llx" into the format
string, but I had no idea what the correct thing to use was. I'm sure
glad to have access to such a knowledgeable community where I can learn
for the low cost of exposing my ignorance in public.

I did verify the above in a copy of WG14/N1124. For anyone that doesn't
recognize that, that's the draft from the C99 working group that I've
been told is remarkably similar to C99 but distinct in that it's freely
available[*]. I haven't verified the similarity, but I have found that
document quite useful in cases like this one.

Thanks for the fix. I'll likely push my change out now that I've added
this fix.

-Carl

[*] http://www.open-std.org/JTC1/SC22/wg14/www/docs/n1124.pdf

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] Switch from random to sequential thread identifiers.

[Carl Worth]

[-- Attachment #1: Type: text/plain, Size: 826 bytes --]

On Tue, 09 Feb 2010 11:35:39 +0100, "Sebastian Spaeth" <Sebastian@SSpaeth.de> wrote:
> On Mon, 08 Feb 2010 13:36:14 -0800, Carl Worth <cworth@cworth.org> wrote:
> > -NOTMUCH_THREAD_ID_SQUELCH='s/thread:................................/thread:XXX/'
> > +NOTMUCH_THREAD_ID_SQUELCH='s/thread:..................../thread:XXX/'
> 
> Caught you not running your test suite before submitting v2 of a patch!
> :-)

Drat, I'm exposed.

And silly of me since this patch is what enables the test suite to
complete in less than 2 seconds now. So I really don't have any excuse
to not run it anymore.

Anyway, I do appreciate all the review. I haven't seen any complaints,
so I'll go ahead and push these changes out, (a version 3 including a
fix for the above...and which I *have* tested with the test suite).

-Carl


[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] Switch from random to sequential thread identifiers.

[Jed Brown]

On Tue, 09 Feb 2010 11:19:54 -0800, Carl Worth <cworth@cworth.org> wrote:
> I did verify the above in a copy of WG14/N1124. For anyone that doesn't
> recognize that, that's the draft from the C99 working group that I've
> been told is remarkably similar to C99 but distinct in that it's freely
> available[*]. I haven't verified the similarity, but I have found that
> document quite useful in cases like this one.

This one is more recent (TC3):

  http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf

I don't know the legality of this copy:

  http://www.ishiboo.com/~danny/c++/C_STANDARD-ISOIEC9899-1999.pdf


Jed