journal: beef up journal matches considerably

we now can take multiple matches, and they will apply as AND if they
apply to different fields and OR if they apply to the same fields. Also,
terms of this kind can be combined with an overreaching OR.

13 files changed, 974 insertions, 347 deletions

diff --git a/.gitignore b/.gitignore
index 07321768a6..c4a7b0ddec 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,5 @@
+/test-journal-match
+/test-journal-stream
 /test-unit-name
 /systemd-system-update-generator
 /systemd-fstab-generator
diff --git a/Makefile.am b/Makefile.am
index aedd22052b..14f9455b51 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -2232,29 +2232,13 @@ journalctl_LDADD = \
 	libsystemd-logs.la
 
 test_journal_SOURCES = \
-	src/journal/test-journal.c \
-	src/journal/sd-journal.c \
-	src/journal/journal-file.c \
-	src/journal/lookup3.c \
-	src/journal/journal-send.c
+	src/journal/test-journal.c
 
 test_journal_LDADD = \
-	libsystemd-label.la \
 	libsystemd-shared.la \
+	libsystemd-journal-internal.la \
 	libsystemd-id128-internal.la
 
-if HAVE_XZ
-test_journal_SOURCES += \
-	src/journal/compress.c
-
-test_journal_CFLAGS = \
-	$(AM_CFLAGS) \
-	$(XZ_CFLAGS)
-
-test_journal_LDADD += \
-	$(XZ_LIBS)
-endif
-
 test_journal_send_SOURCES = \
 	src/journal/test-journal-send.c
 
@@ -2263,6 +2247,22 @@ test_journal_send_LDADD = \
 	libsystemd-journal-internal.la \
 	libsystemd-id128-internal.la
 
+test_journal_match_SOURCES = \
+	src/journal/test-journal-match.c
+
+test_journal_match_LDADD = \
+	libsystemd-shared.la \
+	libsystemd-journal-internal.la \
+	libsystemd-id128-internal.la
+
+test_journal_stream_SOURCES = \
+	src/journal/test-journal-stream.c
+
+test_journal_stream_LDADD = \
+	libsystemd-shared.la \
+	libsystemd-journal-internal.la \
+	libsystemd-id128-internal.la
+
 libsystemd_journal_la_SOURCES = \
 	src/journal/sd-journal.c \
 	src/journal/journal-file.c \
@@ -2327,7 +2327,9 @@ UNINSTALL_EXEC_HOOKS += \
 
 noinst_PROGRAMS += \
 	test-journal \
-	test-journal-send
+	test-journal-send \
+	test-journal-match \
+	test-journal-stream
 
 pkginclude_HEADERS += \
 	src/systemd/sd-journal.h \
diff --git a/man/journalctl.xml b/man/journalctl.xml
index bb964b01ed..f314fb6d26 100644
--- a/man/journalctl.xml
+++ b/man/journalctl.xml
@@ -49,7 +49,7 @@
 
         <refsynopsisdiv>
                 <cmdsynopsis>
-                        <command>journalctl <arg choice="opt" rep="repeat">OPTIONS</arg> <arg choice="opt">MATCH</arg></command>
+                        <command>journalctl <arg choice="opt" rep="repeat">OPTIONS</arg> <arg choice="opt" rep="repeat">MATCHES</arg></command>
                 </cmdsynopsis>
         </refsynopsisdiv>
 
@@ -66,12 +66,25 @@
                 contents of the journal, starting with the oldest
                 entry collected.</para>
 
-                <para>If a match argument is passed the output is
-                filtered accordingly. A match is in the format
-                <literal>FIELD=VALUE</literal>,
-                e.g. <literal>_SYSTEMD_UNIT=httpd.service</literal>. See
+                <para>If one or more match arguments are passed the
+                output is filtered accordingly. A match is in the
+                format <literal>FIELD=VALUE</literal>,
+                e.g. <literal>_SYSTEMD_UNIT=httpd.service</literal>,
+                referring to the components of a structured journal
+                entry. See
                 <citerefentry><refentrytitle>systemd.journal-fields</refentrytitle><manvolnum>7</manvolnum></citerefentry>
-                for a list of well-known fields.</para>
+                for a list of well-known fields. If multiple matches
+                are specified matching different fields the log
+                entries are filtered by both, i.e. the resulting output
+                will show only entries matching all the specified
+                matches of this kind. If two matches apply to the same
+                field, then they are automatically matched as
+                alternatives, i.e. the resulting output will show
+                entries matching any of the specified matches for the
+                same field. Finally, if the character
+                "<literal>+</literal>" appears as separate word on the
+                command line all matches before and after are combined
+                in a disjunction (i.e. logical OR).</para>
 
                 <para>Output is interleaved from all accessible
                 journal files, whether they are rotated or currently
@@ -272,6 +285,37 @@
         </refsect1>
 
         <refsect1>
+                <title>Examples</title>
+
+                <para>Without arguments all collected logs are shown
+                unfiltered:</para>
+
+                <programlisting>journalctl</programlisting>
+
+                <para>With one match specified all entries with a field matching the expression are shown:</para>
+
+                <programlisting>journalctl _SYSTEMD_UNIT=avahi-daemon.service</programlisting>
+
+                <para>If two different fields are matched only entries matching both expressions at the same time are shown:</para>
+
+                <programlisting>journalctl _SYSTEMD_UNIT=avahi-daemon.service _PID=28097</programlisting>
+
+                <para>If two matches refer to the same field all entries matching either expression are shown:</para>
+
+                <programlisting>journalctl _SYSTEMD_UNIT=avahi-daemon.service _SYSTEMD_UNIT=dbus.service</programlisting>
+
+                <para>If the separator "<literal>+</literal>" is used
+                two expression may be combined in a logical OR. The
+                following will show all messages from the Avahi
+                service process with the PID 28097 plus all messages
+                from the D-Bus service (from any of its
+                processes):</para>
+
+                <programlisting>journalctl _SYSTEMD_UNIT=avahi-daemon.service _PID=28097 + _SYSTEMD_UNIT=dbus.service</programlisting>
+
+        </refsect1>
+
+        <refsect1>
                 <title>See Also</title>
                 <para>
                         <citerefentry><refentrytitle>systemd</refentrytitle><manvolnum>1</manvolnum></citerefentry>,
diff --git a/man/systemd.journal-fields.xml b/man/systemd.journal-fields.xml
index fd0beb968f..4f664f43e5 100644
--- a/man/systemd.journal-fields.xml
+++ b/man/systemd.journal-fields.xml
@@ -299,7 +299,12 @@
                 addresses of journal entries are serialized into
                 fields prefixed with double underscores. Note that
                 these aren't proper fields when stored in the journal,
-                but addressing meta data of entries.</para>
+                but addressing meta data of entries. They cannot be
+                written as part of structured log entries via calls
+                such as
+                <citerefentry><refentrytitle>sd_journal_send</refentrytitle><manvolnum>3</manvolnum></citerefentry>. They
+                may also not be used as matches for
+                <citerefentry><refentrytitle>sd_journal_add_match</refentrytitle><manvolnum>3</manvolnum></citerefentry></para>
 
                 <variablelist>
                         <varlistentry>
diff --git a/src/journal/journal-file.c b/src/journal/journal-file.c
index 9665a0535b..0aada9c419 100644
--- a/src/journal/journal-file.c
+++ b/src/journal/journal-file.c
@@ -1212,8 +1212,15 @@ static int generic_array_bisect(JournalFile *f,
                         }
                 }
 
-                if (k > n)
+                if (k > n) {
+                        if (direction == DIRECTION_UP) {
+                                i = n;
+                                subtract_one = true;
+                                goto found;
+                        }
+
                         return 0;
+                }
 
                 last_p = lp;
 
@@ -1246,7 +1253,7 @@ found:
                 *offset = p;
 
         if (idx)
-                *idx = t + i - (subtract_one ? 1 : 0);
+                *idx = t + i + (subtract_one ? -1 : 0);
 
         return 1;
 }
@@ -1263,6 +1270,8 @@ static int generic_array_bisect_plus_one(JournalFile *f,
                                          uint64_t *idx) {
 
         int r;
+        bool step_back = false;
+        Object *o;
 
         assert(f);
         assert(test_object);
@@ -1279,33 +1288,77 @@ static int generic_array_bisect_plus_one(JournalFile *f,
         if (r == TEST_FOUND)
                 r = direction == DIRECTION_DOWN ? TEST_RIGHT : TEST_LEFT;
 
-        if (r == TEST_RIGHT) {
-                Object *o;
-
-                r = journal_file_move_to_object(f, OBJECT_ENTRY, extra, &o);
-                if (r < 0)
-                        return r;
+        /* if we are looking with DIRECTION_UP then we need to first
+           see if in the actual array there is a matching entry, and
+           return the last one of that. But if there isn't any we need
+           to return this one. Hence remember this, and return it
+           below. */
+        if (r == TEST_LEFT)
+                step_back = direction == DIRECTION_UP;
 
-                if (ret)
-                        *ret = o;
-
-                if (offset)
-                        *offset = extra;
-
-                if (idx)
-                        *idx = 0;
-
-                return 1;
+        if (r == TEST_RIGHT) {
+                if (direction == DIRECTION_DOWN)
+                        goto found;
+                else
+                        return 0;
         }
 
         r = generic_array_bisect(f, first, n-1, needle, test_object, direction, ret, offset, idx);
 
+        if (r == 0 && step_back)
+                goto found;
+
         if (r > 0 && idx)
                 (*idx) ++;
 
         return r;
+
+found:
+        r = journal_file_move_to_object(f, OBJECT_ENTRY, extra, &o);
+        if (r < 0)
+                return r;
+
+        if (ret)
+                *ret = o;
+
+        if (offset)
+                *offset = extra;
+
+        if (idx)
+                *idx = 0;
+
+        return 1;
+}
+
+static int test_object_offset(JournalFile *f, uint64_t p, uint64_t needle) {
+        assert(f);
+        assert(p > 0);
+
+        if (p == needle)
+                return TEST_FOUND;
+        else if (p < needle)
+                return TEST_LEFT;
+        else
+                return TEST_RIGHT;
+}
+
+int journal_file_move_to_entry_by_offset(
+                JournalFile *f,
+                uint64_t p,
+                direction_t direction,
+                Object **ret,
+                uint64_t *offset) {
+
+        return generic_array_bisect(f,
+                                    le64toh(f->header->entry_array_offset),
+                                    le64toh(f->header->n_entries),
+                                    p,
+                                    test_object_offset,
+                                    direction,
+                                    ret, offset, NULL);
 }
 
+
 static int test_object_seqnum(JournalFile *f, uint64_t p, uint64_t needle) {
         Object *o;
         int r;
@@ -1407,12 +1460,13 @@ int journal_file_move_to_entry_by_monotonic(
         Object *o;
         int r;
 
-        sd_id128_to_string(boot_id, t + 9);
+        assert(f);
 
+        sd_id128_to_string(boot_id, t + 9);
         r = journal_file_find_data_object(f, t, strlen(t), &o, NULL);
         if (r < 0)
                 return r;
-        else if (r == 0)
+        if (r == 0)
                 return -ENOENT;
 
         return generic_array_bisect_plus_one(f,
@@ -1425,18 +1479,6 @@ int journal_file_move_to_entry_by_monotonic(
                                              ret, offset, NULL);
 }
 
-static int test_object_offset(JournalFile *f, uint64_t p, uint64_t needle) {
-        assert(f);
-        assert(p > 0);
-
-        if (p == needle)
-                return TEST_FOUND;
-        else if (p < needle)
-                return TEST_LEFT;
-        else
-                return TEST_RIGHT;
-}
-
 int journal_file_next_entry(
                 JournalFile *f,
                 Object *o, uint64_t p,
@@ -1601,6 +1643,119 @@ int journal_file_next_entry_for_data(
                                           ret, offset);
 }
 
+int journal_file_move_to_entry_by_offset_for_data(
+                JournalFile *f,
+                uint64_t data_offset,
+                uint64_t p,
+                direction_t direction,
+                Object **ret, uint64_t *offset) {
+
+        int r;
+        Object *d;
+
+        assert(f);
+
+        r = journal_file_move_to_object(f, OBJECT_DATA, data_offset, &d);
+        if (r < 0)
+                return r;
+
+        return generic_array_bisect_plus_one(f,
+                                             le64toh(d->data.entry_offset),
+                                             le64toh(d->data.entry_array_offset),
+                                             le64toh(d->data.n_entries),
+                                             p,
+                                             test_object_offset,
+                                             direction,
+                                             ret, offset, NULL);
+}
+
+int journal_file_move_to_entry_by_monotonic_for_data(
+                JournalFile *f,
+                uint64_t data_offset,
+                sd_id128_t boot_id,
+                uint64_t monotonic,
+                direction_t direction,
+                Object **ret, uint64_t *offset) {
+
+        char t[9+32+1] = "_BOOT_ID=";
+        Object *o, *d;
+        int r;
+        uint64_t b, z;
+
+        assert(f);
+
+        /* First, seek by time */
+        sd_id128_to_string(boot_id, t + 9);
+        r = journal_file_find_data_object(f, t, strlen(t), &o, &b);
+        if (r < 0)
+                return r;
+        if (r == 0)
+                return -ENOENT;
+
+        r = generic_array_bisect_plus_one(f,
+                                          le64toh(o->data.entry_offset),
+                                          le64toh(o->data.entry_array_offset),
+                                          le64toh(o->data.n_entries),
+                                          monotonic,
+                                          test_object_monotonic,
+                                          direction,
+                                          NULL, &z, NULL);
+        if (r <= 0)
+                return r;
+
+        /* And now, continue seeking until we find an entry that
+         * exists in both bisection arrays */
+
+        for (;;) {
+                Object *qo;
+                uint64_t p, q;
+
+                r = journal_file_move_to_object(f, OBJECT_DATA, data_offset, &d);
+                if (r < 0)
+                        return r;
+
+                r = generic_array_bisect_plus_one(f,
+                                                  le64toh(d->data.entry_offset),
+                                                  le64toh(d->data.entry_array_offset),
+                                                  le64toh(d->data.n_entries),
+                                                  z,
+                                                  test_object_offset,
+                                                  direction,
+                                                  NULL, &p, NULL);
+                if (r <= 0)
+                        return r;
+
+                r = journal_file_move_to_object(f, OBJECT_DATA, b, &o);
+                if (r < 0)
+                        return r;
+
+                r = generic_array_bisect_plus_one(f,
+                                                  le64toh(o->data.entry_offset),
+                                                  le64toh(o->data.entry_array_offset),
+                                                  le64toh(o->data.n_entries),
+                                                  p,
+                                                  test_object_offset,
+                                                  direction,
+                                                  &qo, &q, NULL);
+
+                if (r <= 0)
+                        return r;
+
+                if (p == q) {
+                        if (ret)
+                                *ret = qo;
+                        if (offset)
+                                *offset = q;
+
+                        return 1;
+                }
+
+                z = q;
+        }
+
+        return 0;
+}
+
 int journal_file_move_to_entry_by_seqnum_for_data(
                 JournalFile *f,
                 uint64_t data_offset,
diff --git a/src/journal/journal-file.h b/src/journal/journal-file.h
index a9925c0754..5c42ecdf6c 100644
--- a/src/journal/journal-file.h
+++ b/src/journal/journal-file.h
@@ -43,6 +43,7 @@ enum {
         WINDOW_DATA_HASH_TABLE = OBJECT_DATA_HASH_TABLE,
         WINDOW_FIELD_HASH_TABLE = OBJECT_FIELD_HASH_TABLE,
         WINDOW_ENTRY_ARRAY = OBJECT_ENTRY_ARRAY,
+        WINDOW_SIGNATURE = OBJECT_SIGNATURE,
         WINDOW_HEADER,
         _WINDOW_MAX
 };
@@ -106,12 +107,15 @@ int journal_file_skip_entry(JournalFile *f, Object *o, uint64_t p, int64_t skip,
 
 int journal_file_next_entry_for_data(JournalFile *f, Object *o, uint64_t p, uint64_t data_offset, direction_t direction, Object **ret, uint64_t *offset);
 
+int journal_file_move_to_entry_by_offset(JournalFile *f, uint64_t seqnum, direction_t direction, Object **ret, uint64_t *offset);
 int journal_file_move_to_entry_by_seqnum(JournalFile *f, uint64_t seqnum, direction_t direction, Object **ret, uint64_t *offset);
 int journal_file_move_to_entry_by_realtime(JournalFile *f, uint64_t realtime, direction_t direction, Object **ret, uint64_t *offset);
 int journal_file_move_to_entry_by_monotonic(JournalFile *f, sd_id128_t boot_id, uint64_t monotonic, direction_t direction, Object **ret, uint64_t *offset);
 
+int journal_file_move_to_entry_by_offset_for_data(JournalFile *f, uint64_t data_offset, uint64_t p, direction_t direction, Object **ret, uint64_t *offset);
 int journal_file_move_to_entry_by_seqnum_for_data(JournalFile *f, uint64_t data_offset, uint64_t seqnum, direction_t direction, Object **ret, uint64_t *offset);
 int journal_file_move_to_entry_by_realtime_for_data(JournalFile *f, uint64_t data_offset, uint64_t realtime, direction_t direction, Object **ret, uint64_t *offset);
+int journal_file_move_to_entry_by_monotonic_for_data(JournalFile *f, uint64_t data_offset, sd_id128_t boot_id, uint64_t monotonic, direction_t direction, Object **ret, uint64_t *offset);
 
 int journal_file_copy_entry(JournalFile *from, JournalFile *to, Object *o, uint64_t p, uint64_t *seqnum, Object **ret, uint64_t *offset);
 
diff --git a/src/journal/journal-internal.h b/src/journal/journal-internal.h
index 929dfcdcb8..482ef61b9a 100644
--- a/src/journal/journal-internal.h
+++ b/src/journal/journal-internal.h
@@ -28,28 +28,46 @@
 
 #include <systemd/sd-id128.h>
 
+#include "journal-def.h"
 #include "list.h"
+#include "hashmap.h"
+#include "journal-file.h"
+
+typedef enum MatchType MatchType;
+typedef enum LocationType LocationType;
 
 typedef struct Match Match;
 typedef struct Location Location;
 typedef struct Directory Directory;
 
-typedef enum location_type {
-        LOCATION_HEAD,
-        LOCATION_TAIL,
-        LOCATION_DISCRETE
-} location_type_t;
+typedef enum MatchType {
+        MATCH_DISCRETE,
+        MATCH_OR_TERM,
+        MATCH_AND_TERM
+} MatchType;
 
 struct Match {
+        MatchType type;
+        Match *parent;
+        LIST_FIELDS(Match, matches);
+
+        /* For concrete matches */
         char *data;
         size_t size;
         le64_t le_hash;
 
-        LIST_FIELDS(Match, matches);
+        /* For terms */
+        LIST_HEAD(Match, matches);
 };
 
+typedef enum LocationType {
+        LOCATION_HEAD,
+        LOCATION_TAIL,
+        LOCATION_DISCRETE
+} LocationType;
+
 struct Location {
-        location_type_t type;
+        LocationType type;
 
         uint64_t seqnum;
         sd_id128_t seqnum_id;
@@ -78,6 +96,7 @@ struct sd_journal {
         Hashmap *files;
 
         Location current_location;
+
         JournalFile *current_file;
         uint64_t current_field;
 
@@ -86,10 +105,11 @@ struct sd_journal {
 
         int inotify_fd;
 
-        LIST_HEAD(Match, matches);
-        unsigned n_matches;
+        Match *level0, *level1;
 
         unsigned current_invalidate_counter, last_invalidate_counter;
 };
 
+char *journal_make_match_string(sd_journal *j);
+
 #endif
diff --git a/src/journal/journalctl.c b/src/journal/journalctl.c
index 43cd2a3fef..65b3bd5a86 100644
--- a/src/journal/journalctl.c
+++ b/src/journal/journalctl.c
@@ -225,7 +225,9 @@ static int add_matches(sd_journal *j, char **args) {
 
         STRV_FOREACH(i, args) {
 
-                if (path_is_absolute(*i)) {
+                if (streq(*i, "+"))
+                        r = sd_journal_add_disjunction(j);
+                else if (path_is_absolute(*i)) {
                         char *p;
                         const char *path;
                         struct stat st;
@@ -249,7 +251,7 @@ static int add_matches(sd_journal *j, char **args) {
                                         return -ENOMEM;
                                 }
 
-                                r = sd_journal_add_match(j, t, strlen(t));
+                                r = sd_journal_add_match(j, t, 0);
                                 free(t);
                         } else {
                                 free(p);
@@ -259,10 +261,10 @@ static int add_matches(sd_journal *j, char **args) {
 
                         free(p);
                 } else
-                        r = sd_journal_add_match(j, *i, strlen(*i));
+                        r = sd_journal_add_match(j, *i, 0);
 
                 if (r < 0) {
-                        log_error("Failed to add match: %s", strerror(-r));
+                        log_error("Failed to add match '%s': %s", *i, strerror(-r));
                         return r;
                 }
         }
diff --git a/src/journal/sd-journal.c b/src/journal/sd-journal.c
index f4ef1aea7c..4bcc65c5c7 100644
--- a/src/journal/sd-journal.c
+++ b/src/journal/sd-journal.c
@@ -87,102 +87,272 @@ static void set_location(sd_journal *j, JournalFile *f, Object *o, uint64_t offs
         f->current_offset = offset;
 }
 
-static int same_field(const void *_a, size_t s, const void *_b, size_t t) {
+static int match_is_valid(const void *data, size_t size) {
+        const char *b, *p;
+
+        assert(data);
+
+        if (size < 2)
+                return false;
+
+        if (startswith(data, "__"))
+                return false;
+
+        b = data;
+        for (p = b; p < b + size; p++) {
+
+                if (*p == '=')
+                        return p > b;
+
+                if (*p == '_')
+                        continue;
+
+                if (*p >= 'A' && *p <= 'Z')
+                        continue;
+
+                if (*p >= '0' && *p <= '9')
+                        continue;
+
+                return false;
+        }
+
+        return false;
+}
+
+static bool same_field(const void *_a, size_t s, const void *_b, size_t t) {
         const uint8_t *a = _a, *b = _b;
         size_t j;
-        bool a_good = false, b_good = false, different = false;
 
         for (j = 0; j < s && j < t; j++) {
 
-                if (a[j] == '=')
-                        a_good = true;
-                if (b[j] == '=')
-                        b_good = true;
                 if (a[j] != b[j])
-                        different = true;
+                        return false;
+
+                if (a[j] == '=')
+                        return true;
+        }
+
+        return true;
+}
+
+static Match *match_new(Match *p, MatchType t) {
+        Match *m;
 
-                if (a_good && b_good)
-                        return different ? 0 : 1;
+        m = new0(Match, 1);
+        if (!m)
+                return NULL;
+
+        m->type = t;
+
+        if (p) {
+                m->parent = p;
+                LIST_PREPEND(Match, matches, p->matches, m);
         }
 
-        return -EINVAL;
+        return m;
+}
+
+static void match_free(Match *m) {
+        assert(m);
+
+        while (m->matches)
+                match_free(m->matches);
+
+        if (m->parent)
+                LIST_REMOVE(Match, matches, m->parent->matches, m);
+
+        free(m->data);
+        free(m);
+}
+
+static void match_free_if_empty(Match *m) {
+        assert(m);
+
+        if (m->matches)
+                return;
+
+        match_free(m);
 }
 
 _public_ int sd_journal_add_match(sd_journal *j, const void *data, size_t size) {
-        Match *m, *after = NULL;
+        Match *l2, *l3, *add_here = NULL, *m;
         le64_t le_hash;
 
         if (!j)
                 return -EINVAL;
+
         if (!data)
                 return -EINVAL;
-        if (size <= 1)
-                return -EINVAL;
-        if (!memchr(data, '=', size))
-                return -EINVAL;
-        if (*(char*) data == '=')
+
+        if (size == 0)
+                size = strlen(data);
+
+        if (!match_is_valid(data, size))
                 return -EINVAL;
 
-        /* FIXME: iterating with multiple matches is currently
-         * broken */
-        if (j->matches)
-                return -ENOTSUP;
+        /* level 0: OR term
+         * level 1: AND terms
+         * level 2: OR terms
+         * level 3: concrete matches */
+
+        if (!j->level0) {
+                j->level0 = match_new(NULL, MATCH_OR_TERM);
+                if (!j->level0)
+                        return -ENOMEM;
+        }
+
+        if (!j->level1) {
+                j->level1 = match_new(j->level0, MATCH_AND_TERM);
+                if (!j->level1)
+                        return -ENOMEM;
+        }
+
+        assert(j->level0->type == MATCH_OR_TERM);
+        assert(j->level1->type == MATCH_AND_TERM);
 
         le_hash = htole64(hash64(data, size));
 
-        LIST_FOREACH(matches, m, j->matches) {
-                int r;
+        LIST_FOREACH(matches, l2, j->level1->matches) {
+                assert(l2->type == MATCH_OR_TERM);
 
-                if (m->le_hash == le_hash &&
-                    m->size == size &&
-                    memcmp(m->data, data, size) == 0)
-                        return 0;
+                LIST_FOREACH(matches, l3, l2->matches) {
+                        assert(l3->type == MATCH_DISCRETE);
 
-                r = same_field(data, size, m->data, m->size);
-                if (r < 0)
-                        return r;
-                else if (r > 0)
-                        after = m;
+                        /* Exactly the same match already? Then ignore
+                         * this addition */
+                        if (l3->le_hash == le_hash &&
+                            l3->size == size &&
+                            memcmp(l3->data, data, size) == 0)
+                                return 0;
+
+                        /* Same field? Then let's add this to this OR term */
+                        if (same_field(data, size, l3->data, l3->size)) {
+                                add_here = l2;
+                                break;
+                        }
+                }
+
+                if (add_here)
+                        break;
         }
 
-        m = new0(Match, 1);
+        if (!add_here) {
+                add_here = match_new(j->level1, MATCH_OR_TERM);
+                if (!add_here)
+                        goto fail;
+        }
+
+        m = match_new(add_here, MATCH_DISCRETE);
         if (!m)
-                return -ENOMEM;
+                goto fail;
 
+        m->le_hash = le_hash;
         m->size = size;
+        m->data = memdup(data, size);
+        if (!m->data)
+                goto fail;
+
+        detach_location(j);
+
+        return 0;
+
+fail:
+        if (add_here)
+                match_free_if_empty(add_here);
+
+        if (j->level1)
+                match_free_if_empty(j->level1);
+
+        if (j->level0)
+                match_free_if_empty(j->level0);
+
+        return -ENOMEM;
+}
+
+_public_ int sd_journal_add_disjunction(sd_journal *j) {
+        Match *m;
+
+        assert(j);
+
+        if (!j->level0)
+                return 0;
+
+        if (!j->level1)
+                return 0;
 
-        m->data = malloc(m->size);
-        if (!m->data) {
-                free(m);
+        if (!j->level1->matches)
+                return 0;
+
+        m = match_new(j->level0, MATCH_AND_TERM);
+        if (!m)
                 return -ENOMEM;
+
+        j->level1 = m;
+        return 0;
+}
+
+static char *match_make_string(Match *m) {
+        char *p, *r;
+        Match *i;
+        bool enclose = false;
+
+        if (!m)
+                return strdup("");
+
+        if (m->type == MATCH_DISCRETE)
+                return strndup(m->data, m->size);
+
+        p = NULL;
+        LIST_FOREACH(matches, i, m->matches) {
+                char *t, *k;
+
+                t = match_make_string(i);
+                if (!t) {
+                        free(p);
+                        return NULL;
+                }
+
+                if (p) {
+                        k = join(p, m->type == MATCH_OR_TERM ? " OR " : " AND ", t, NULL);
+                        free(p);
+                        free(t);
+
+                        if (!k)
+                                return NULL;
+
+                        p = k;
+
+                        enclose = true;
+                } else {
+                        free(p);
+                        p = t;
+                }
         }
 
-        memcpy(m->data, data, size);
-        m->le_hash = le_hash;
+        if (enclose) {
+                r = join("(", p, ")", NULL);
+                free(p);
+                return r;
+        }
 
-        /* Matches for the same fields we order adjacent to each
-         * other */
-        LIST_INSERT_AFTER(Match, matches, j->matches, after, m);
-        j->n_matches ++;
+        return p;
+}
 
-        detach_location(j);
+char *journal_make_match_string(sd_journal *j) {
+        assert(j);
 
-        return 0;
+        return match_make_string(j->level0);
 }
 
 _public_ void sd_journal_flush_matches(sd_journal *j) {
+
         if (!j)
                 return;
 
-        while (j->matches) {
-                Match *m = j->matches;
+        if (j->level0)
+                match_free(j->level0);
 
-                LIST_REMOVE(Match, matches, j->matches, m);
-                free(m->data);
-                free(m);
-        }
-
-        j->n_matches = 0;
+        j->level0 = j->level1 = NULL;
 
         detach_location(j);
 }
@@ -319,290 +489,270 @@ static int compare_with_location(JournalFile *af, Object *ao, Location *l) {
         return 0;
 }
 
-static int find_location(sd_journal *j, JournalFile *f, direction_t direction, Object **ret, uint64_t *offset) {
-        Object *o = NULL;
-        uint64_t p = 0;
+static int next_for_match(
+                sd_journal *j,
+                Match *m,
+                JournalFile *f,
+                uint64_t after_offset,
+                direction_t direction,
+                Object **ret,
+                uint64_t *offset) {
+
         int r;
+        uint64_t np = 0;
+        Object *n;
 
         assert(j);
+        assert(m);
+        assert(f);
 
-        if (!j->matches) {
-                /* No matches is simple */
-
-                if (j->current_location.type == LOCATION_HEAD)
-                        r = journal_file_next_entry(f, NULL, 0, DIRECTION_DOWN, &o, &p);
-                else if (j->current_location.type == LOCATION_TAIL)
-                        r = journal_file_next_entry(f, NULL, 0, DIRECTION_UP, &o, &p);
-                else if (j->current_location.seqnum_set &&
-                         sd_id128_equal(j->current_location.seqnum_id, f->header->seqnum_id))
-                        r = journal_file_move_to_entry_by_seqnum(f, j->current_location.seqnum, direction, &o, &p);
-                else if (j->current_location.monotonic_set) {
-                        r = journal_file_move_to_entry_by_monotonic(f, j->current_location.boot_id, j->current_location.monotonic, direction, &o, &p);
-
-                        if (r == -ENOENT) {
-                                /* boot id unknown in this file */
-                                if (j->current_location.realtime_set)
-                                        r = journal_file_move_to_entry_by_realtime(f, j->current_location.realtime, direction, &o, &p);
-                                else
-                                        r = journal_file_next_entry(f, NULL, 0, direction, &o, &p);
-                        }
-                } else if (j->current_location.realtime_set)
-                        r = journal_file_move_to_entry_by_realtime(f, j->current_location.realtime, direction, &o, &p);
-                else
-                        r = journal_file_next_entry(f, NULL, 0, direction, &o, &p);
+        if (m->type == MATCH_DISCRETE) {
+                uint64_t dp;
 
+                r = journal_file_find_data_object_with_hash(f, m->data, m->size, le64toh(m->le_hash), NULL, &dp);
                 if (r <= 0)
                         return r;
 
-        } else  {
-                Match *m, *term_match = NULL;
-                Object *to = NULL;
-                uint64_t tp = 0;
+                return journal_file_move_to_entry_by_offset_for_data(f, dp, after_offset, direction, ret, offset);
 
-                /* We have matches, first, let's jump to the monotonic
-                 * position if we have any, since it implies a
-                 * match. */
+        } else if (m->type == MATCH_OR_TERM) {
+                Match *i;
 
-                if (j->current_location.type == LOCATION_DISCRETE &&
-                    j->current_location.monotonic_set) {
+                /* Find the earliest match beyond after_offset */
 
-                        r = journal_file_move_to_entry_by_monotonic(f, j->current_location.boot_id, j->current_location.monotonic, direction, &o, &p);
-                        if (r <= 0)
-                                return r == -ENOENT ? 0 : r;
-                }
-
-                LIST_FOREACH(matches, m, j->matches) {
-                        Object *c, *d;
-                        uint64_t cp, dp;
-
-                        r = journal_file_find_data_object_with_hash(f, m->data, m->size, le64toh(m->le_hash), &d, &dp);
-                        if (r <= 0)
-                                return r;
-
-                        if (j->current_location.type == LOCATION_HEAD)
-                                r = journal_file_next_entry_for_data(f, NULL, 0, dp, DIRECTION_DOWN, &c, &cp);
-                        else if (j->current_location.type == LOCATION_TAIL)
-                                r = journal_file_next_entry_for_data(f, NULL, 0, dp, DIRECTION_UP, &c, &cp);
-                        else if (j->current_location.seqnum_set &&
-                                 sd_id128_equal(j->current_location.seqnum_id, f->header->seqnum_id))
-                                r = journal_file_move_to_entry_by_seqnum_for_data(f, dp, j->current_location.seqnum, direction, &c, &cp);
-                        else if (j->current_location.realtime_set)
-                                r = journal_file_move_to_entry_by_realtime_for_data(f, dp, j->current_location.realtime, direction, &c, &cp);
-                        else
-                                r = journal_file_next_entry_for_data(f, NULL, 0, dp, direction, &c, &cp);
+                LIST_FOREACH(matches, i, m->matches) {
+                        uint64_t cp;
 
+                        r = next_for_match(j, i, f, after_offset, direction, NULL, &cp);
                         if (r < 0)
                                 return r;
+                        else if (r > 0) {
+                                if (np == 0 || (direction == DIRECTION_DOWN ? np > cp : np < cp))
+                                        np = cp;
+                        }
+                }
 
-                        if (!term_match) {
-                                term_match = m;
-
-                                if (r > 0) {
-                                        to = c;
-                                        tp = cp;
-                                }
-                        } else if (same_field(term_match->data, term_match->size, m->data, m->size)) {
-
-                                /* Same field as previous match... */
-                                if (r > 0) {
-
-                                        /* Find the earliest of the OR matches */
+        } else if (m->type == MATCH_AND_TERM) {
+                Match *i;
+                bool continue_looking;
 
-                                        if (!to ||
-                                            (direction == DIRECTION_DOWN && cp < tp) ||
-                                            (direction == DIRECTION_UP && cp > tp)) {
-                                                to = c;
-                                                tp = cp;
-                                        }
+                /* Always jump to the next matching entry and repeat
+                 * this until we fine and offset that matches for all
+                 * matches. */
 
-                                }
+                if (!m->matches)
+                        return 0;
 
-                        } else {
+                np = 0;
+                do {
+                        continue_looking = false;
 
-                                /* Previous term is finished, did anything match? */
-                                if (!to)
-                                        return 0;
+                        LIST_FOREACH(matches, i, m->matches) {
+                                uint64_t cp, limit;
 
-                                /* Find the last of the AND matches */
-                                if (!o ||
-                                    (direction == DIRECTION_DOWN && tp > p) ||
-                                    (direction == DIRECTION_UP && tp < p)) {
-                                        o = to;
-                                        p = tp;
-                                }
+                                if (np == 0)
+                                        limit = after_offset;
+                                else if (direction == DIRECTION_DOWN)
+                                        limit = MAX(np, after_offset);
+                                else
+                                        limit = MIN(np, after_offset);
 
-                                term_match = m;
+                                r = next_for_match(j, i, f, limit, direction, NULL, &cp);
+                                if (r <= 0)
+                                        return r;
 
-                                if (r > 0) {
-                                        to = c;
-                                        tp = cp;
-                                } else {
-                                        to = NULL;
-                                        tp = 0;
+                                if ((direction == DIRECTION_DOWN ? cp >= after_offset : cp <= after_offset) &&
+                                    (np == 0 || (direction == DIRECTION_DOWN ? cp > np : np < cp))) {
+                                        np = cp;
+                                        continue_looking = true;
                                 }
                         }
-                }
 
-                /* Last term is finished, did anything match? */
-                if (!to)
-                        return 0;
+                } while (continue_looking);
+        }
 
-                if (!o ||
-                    (direction == DIRECTION_DOWN && tp > p) ||
-                    (direction == DIRECTION_UP && tp < p)) {
-                        o = to;
-                        p = tp;
-                }
+        if (np == 0)
+                return 0;
 
-                if (!o)
-                        return 0;
-        }
+        r = journal_file_move_to_object(f, OBJECT_ENTRY, np, &n);
+        if (r < 0)
+                return r;
 
         if (ret)
-                *ret = o;
-
+                *ret = n;
         if (offset)
-                *offset = p;
+                *offset = np;
 
         return 1;
 }
 
-static int next_with_matches(sd_journal *j, JournalFile *f, direction_t direction, Object **ret, uint64_t *offset) {
+static int find_location_for_match(
+                sd_journal *j,
+                Match *m,
+                JournalFile *f,
+                direction_t direction,
+                Object **ret,
+                uint64_t *offset) {
+
         int r;
-        uint64_t cp;
-        Object *c;
 
         assert(j);
+        assert(m);
         assert(f);
-        assert(ret);
-        assert(offset);
 
-        c = *ret;
-        cp = *offset;
+        if (m->type == MATCH_DISCRETE) {
+                uint64_t dp;
 
-        if (!j->matches) {
-                /* No matches is easy */
-
-                r = journal_file_next_entry(f, c, cp, direction, &c, &cp);
+                r = journal_file_find_data_object_with_hash(f, m->data, m->size, le64toh(m->le_hash), NULL, &dp);
                 if (r <= 0)
                         return r;
 
-                if (ret)
-                        *ret = c;
-                if (offset)
-                        *offset = cp;
-                return 1;
-        }
+                /* FIXME: missing: find by monotonic */
+
+                if (j->current_location.type == LOCATION_HEAD)
+                        return journal_file_next_entry_for_data(f, NULL, 0, dp, DIRECTION_DOWN, ret, offset);
+                if (j->current_location.type == LOCATION_TAIL)
+                        return journal_file_next_entry_for_data(f, NULL, 0, dp, DIRECTION_UP, ret, offset);
+                if (j->current_location.seqnum_set && sd_id128_equal(j->current_location.seqnum_id, f->header->seqnum_id))
+                        return journal_file_move_to_entry_by_seqnum_for_data(f, dp, j->current_location.seqnum, direction, ret, offset);
+                if (j->current_location.monotonic_set) {
+                        r = journal_file_move_to_entry_by_monotonic_for_data(f, dp, j->current_location.boot_id, j->current_location.monotonic, direction, ret, offset);
+                        if (r != -ENOENT)
+                                return r;
+                }
+                if (j->current_location.realtime_set)
+                        return journal_file_move_to_entry_by_realtime_for_data(f, dp, j->current_location.realtime, direction, ret, offset);
 
-        /* So there are matches we have to adhere to, let's find the
-         * first entry that matches all of them */
+                return journal_file_next_entry_for_data(f, NULL, 0, dp, direction, ret, offset);
 
-        for (;;) {
-                uint64_t np, n;
-                bool found, term_result = false;
-                Match *m, *term_match = NULL;
-                Object *npo = NULL;
+        } else if (m->type == MATCH_OR_TERM) {
+                uint64_t np = 0;
+                Object *n;
+                Match *i;
 
-                n = journal_file_entry_n_items(c);
+                /* Find the earliest match */
 
-                /* Make sure we don't match the entry we are starting
-                 * from. */
-                found = cp != *offset;
+                LIST_FOREACH(matches, i, m->matches) {
+                        uint64_t cp;
 
-                np = 0;
-                LIST_FOREACH(matches, m, j->matches) {
-                        uint64_t q, k;
-                        Object *qo = NULL;
-
-                        /* Let's check if this is the beginning of a
-                         * new term, i.e. has a different field prefix
-                         * as the preceeding match. */
-                        if (!term_match) {
-                                term_match = m;
-                                term_result = false;
-                        } else if (!same_field(term_match->data, term_match->size, m->data, m->size)) {
-                                if (!term_result)
-                                        found = false;
-
-                                term_match = m;
-                                term_result = false;
+                        r = find_location_for_match(j, i, f, direction, NULL, &cp);
+                        if (r < 0)
+                                return r;
+                        else if (r > 0) {
+                                if (np == 0 || (direction == DIRECTION_DOWN ? np > cp : np < cp))
+                                        np = cp;
                         }
+                }
 
-                        for (k = 0; k < n; k++)
-                                if (c->entry.items[k].hash == m->le_hash)
-                                        break;
+                if (np == 0)
+                        return 0;
 
-                        if (k >= n) {
-                                /* Hmm, didn't find any field that
-                                 * matched this rule, so ignore this
-                                 * match. Go on with next match */
-                                continue;
-                        }
+                r = journal_file_move_to_object(f, OBJECT_ENTRY, np, &n);
+                if (r < 0)
+                        return r;
+
+                if (ret)
+                        *ret = n;
+                if (offset)
+                        *offset = np;
 
-                        term_result = true;
+                return 1;
+
+        } else {
+                Match *i;
+                uint64_t np = 0;
 
-                        /* Hmm, so, this field matched, let's remember
-                         * where we'd have to try next, in case the other
-                         * matches are not OK */
+                assert(m->type == MATCH_AND_TERM);
 
-                        r = journal_file_next_entry_for_data(f, c, cp, le64toh(c->entry.items[k].object_offset), direction, &qo, &q);
-                        /* This pointer is invalidated if the window was
-                         * remapped. May need to re-fetch it later */
-                        c = NULL;
-                        if (r < 0)
+                /* First jump to the last match, and then find the
+                 * next one where all matches match */
+
+                if (!m->matches)
+                        return 0;
+
+                LIST_FOREACH(matches, i, m->matches) {
+                        uint64_t cp;
+
+                        r = find_location_for_match(j, i, f, direction, NULL, &cp);
+                        if (r <= 0)
                                 return r;
 
-                        if (r > 0) {
-
-                                if (direction == DIRECTION_DOWN) {
-                                        if (q > np) {
-                                                np = q;
-                                                npo = qo;
-                                        }
-                                } else {
-                                        if (np == 0 || q < np) {
-                                                np = q;
-                                                npo = qo;
-                                        }
-                                }
-                        }
+                        if (np == 0 || (direction == DIRECTION_DOWN ? np < cp : np > cp))
+                                np = cp;
                 }
 
-                /* Check the last term */
-                if (term_match && !term_result)
-                        found = false;
+                return next_for_match(j, m, f, np, direction, ret, offset);
+        }
+}
 
-                /* Did this entry match against all matches? */
-                if (found) {
-                        if (ret) {
-                                if (c == NULL) {
-                                        /* Re-fetch the entry */
-                                        r = journal_file_move_to_object(f, OBJECT_ENTRY, cp, &c);
-                                        if (r < 0)
-                                                return r;
-                                }
-                                *ret = c;
-                        }
-                        if (offset)
-                                *offset = cp;
-                        return 1;
+static int find_location_with_matches(
+                sd_journal *j,
+                JournalFile *f,
+                direction_t direction,
+                Object **ret,
+                uint64_t *offset) {
+
+        int r;
+
+        assert(j);
+        assert(f);
+        assert(ret);
+        assert(offset);
+
+        if (!j->level0) {
+                /* No matches is simple */
+
+                if (j->current_location.type == LOCATION_HEAD)
+                        return journal_file_next_entry(f, NULL, 0, DIRECTION_DOWN, ret, offset);
+                if (j->current_location.type == LOCATION_TAIL)
+                        return journal_file_next_entry(f, NULL, 0, DIRECTION_UP, ret, offset);
+                if (j->current_location.seqnum_set && sd_id128_equal(j->current_location.seqnum_id, f->header->seqnum_id))
+                        return journal_file_move_to_entry_by_seqnum(f, j->current_location.seqnum, direction, ret, offset);
+                if (j->current_location.monotonic_set) {
+                        r = journal_file_move_to_entry_by_monotonic(f, j->current_location.boot_id, j->current_location.monotonic, direction, ret, offset);
+                        if (r != -ENOENT)
+                                return r;
                 }
+                if (j->current_location.realtime_set)
+                        return journal_file_move_to_entry_by_realtime(f, j->current_location.realtime, direction, ret, offset);
 
-                /* Did we find a subsequent entry? */
-                if (np == 0)
-                        return 0;
+                return journal_file_next_entry(f, NULL, 0, direction, ret, offset);
+        } else
+                return find_location_for_match(j, j->level0, f, direction, ret, offset);
+}
 
-                /* Hmm, ok, this entry only matched partially, so
-                 * let's try another one */
-                cp = np;
-                c = npo;
-        }
+static int next_with_matches(
+                sd_journal *j,
+                JournalFile *f,
+                direction_t direction,
+                Object **ret,
+                uint64_t *offset) {
+
+        Object *c;
+        uint64_t cp;
+
+        assert(j);
+        assert(f);
+        assert(ret);
+        assert(offset);
+
+        c = *ret;
+        cp = *offset;
+
+        /* No matches is easy. We simple advance the file
+         * pointer by one. */
+        if (!j->level0)
+                return journal_file_next_entry(f, c, cp, direction, ret, offset);
+
+        /* If we have a match then we look for the next matching entry
+         * wiht an offset at least one step larger */
+        return next_for_match(j, j->level0, f, direction == DIRECTION_DOWN ? cp+1 : cp-1, direction, ret, offset);
 }
 
 static int next_beyond_location(sd_journal *j, JournalFile *f, direction_t direction, Object **ret, uint64_t *offset) {
         Object *c;
         uint64_t cp;
-        int compare_value, r;
+        int r;
 
         assert(j);
         assert(f);
@@ -617,16 +767,18 @@ static int next_beyond_location(sd_journal *j, JournalFile *f, direction_t direc
                 r = next_with_matches(j, f, direction, &c, &cp);
                 if (r <= 0)
                         return r;
-
-                compare_value = 1;
         } else {
-                r = find_location(j, f, direction, &c, &cp);
+                r = find_location_with_matches(j, f, direction, &c, &cp);
                 if (r <= 0)
                         return r;
-
-                compare_value = 0;
         }
 
+        /* OK, we found the spot, now let's advance until to an entry
+         * that is actually different from what we were previously
+         * looking at. This is necessary to handle entries which exist
+         * in two (or more) journal files, and which shall all be
+         * suppressed but one. */
+
         for (;;) {
                 bool found;
 
@@ -635,9 +787,9 @@ static int next_beyond_location(sd_journal *j, JournalFile *f, direction_t direc
 
                         k = compare_with_location(f, c, &j->current_location);
                         if (direction == DIRECTION_DOWN)
-                                found = k >= compare_value;
+                                found = k > 0;
                         else
-                                found = k <= -compare_value;
+                                found = k < 0;
                 } else
                         found = true;
 
diff --git a/src/journal/test-journal-match.c b/src/journal/test-journal-match.c
new file mode 100644
index 0000000000..fa228144f5
--- /dev/null
+++ b/src/journal/test-journal-match.c
@@ -0,0 +1,67 @@
+/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
+
+/***
+  This file is part of systemd.
+
+  Copyright 2012 Lennart Poettering
+
+  systemd is free software; you can redistribute it and/or modify it
+  under the terms of the GNU Lesser General Public License as published by
+  the Free Software Foundation; either version 2.1 of the License, or
+  (at your option) any later version.
+
+  systemd 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
+  Lesser General Public License for more details.
+
+  You should have received a copy of the GNU Lesser General Public License
+  along with systemd; If not, see <http://www.gnu.org/licenses/>.
+***/
+
+#include <stdio.h>
+
+#include <systemd/sd-journal.h>
+
+#include "journal-internal.h"
+#include "util.h"
+#include "log.h"
+
+int main(int argc, char *argv[]) {
+        sd_journal *j;
+        char *t;
+
+        log_set_max_level(LOG_DEBUG);
+
+        assert_se(sd_journal_open(&j, 0) >= 0);
+
+        assert_se(sd_journal_add_match(j, "foobar", 0) < 0);
+        assert_se(sd_journal_add_match(j, "foobar=waldo", 0) < 0);
+        assert_se(sd_journal_add_match(j, "", 0) < 0);
+        assert_se(sd_journal_add_match(j, "=", 0) < 0);
+        assert_se(sd_journal_add_match(j, "=xxxxx", 0) < 0);
+        assert_se(sd_journal_add_match(j, "HALLO=WALDO", 0) >= 0);
+        assert_se(sd_journal_add_match(j, "QUUX=mmmm", 0) >= 0);
+        assert_se(sd_journal_add_match(j, "QUUX=xxxxx", 0) >= 0);
+        assert_se(sd_journal_add_match(j, "HALLO=", 0) >= 0);
+        assert_se(sd_journal_add_match(j, "QUUX=xxxxx", 0) >= 0);
+        assert_se(sd_journal_add_match(j, "QUUX=yyyyy", 0) >= 0);
+        assert_se(sd_journal_add_match(j, "PIFF=paff", 0) >= 0);
+
+        assert_se(sd_journal_add_disjunction(j) >= 0);
+
+        assert_se(sd_journal_add_match(j, "ONE=one", 0) >= 0);
+        assert_se(sd_journal_add_match(j, "ONE=two", 0) >= 0);
+        assert_se(sd_journal_add_match(j, "TWO=two", 0) >= 0);
+
+        assert_se(t = journal_make_match_string(j));
+
+        assert_se(streq(t, "((TWO=two AND (ONE=two OR ONE=one)) OR (PIFF=paff AND (QUUX=yyyyy OR QUUX=xxxxx OR QUUX=mmmm) AND (HALLO= OR HALLO=WALDO)))"));
+
+        printf("resulting match expression is: %s\n", t);
+        free(t);
+
+        sd_journal_close(j);
+
+        return 0;
+}
diff --git a/src/journal/test-journal-send.c b/src/journal/test-journal-send.c
index d682abbf01..9d376d1e56 100644
--- a/src/journal/test-journal-send.c
+++ b/src/journal/test-journal-send.c
@@ -21,7 +21,11 @@
 
 #include <systemd/sd-journal.h>
 
+#include "log.h"
+
 int main(int argc, char *argv[]) {
+        log_set_max_level(LOG_DEBUG);
+
         sd_journal_print(LOG_INFO, "piepapo");
 
         sd_journal_send("MESSAGE=foobar",
diff --git a/src/journal/test-journal-stream.c b/src/journal/test-journal-stream.c
new file mode 100644
index 0000000000..313606f9be
--- /dev/null
+++ b/src/journal/test-journal-stream.c
@@ -0,0 +1,169 @@
+/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
+
+/***
+  This file is part of systemd.
+
+  Copyright 2012 Lennart Poettering
+
+  systemd is free software; you can redistribute it and/or modify it
+  under the terms of the GNU Lesser General Public License as published by
+  the Free Software Foundation; either version 2.1 of the License, or
+  (at your option) any later version.
+
+  systemd 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
+  Lesser General Public License for more details.
+
+  You should have received a copy of the GNU Lesser General Public License
+  along with systemd; If not, see <http://www.gnu.org/licenses/>.
+***/
+
+#include <unistd.h>
+#include <fcntl.h>
+
+#include <systemd/sd-journal.h>
+
+#include "journal-file.h"
+#include "journal-internal.h"
+#include "util.h"
+#include "log.h"
+
+#define N_ENTRIES 200
+
+static void verify_contents(sd_journal *j, unsigned skip) {
+        unsigned i;
+
+        assert(j);
+
+        i = 0;
+        SD_JOURNAL_FOREACH(j) {
+                const void *d;
+                char *k;
+                size_t l;
+                unsigned u;
+
+                assert_se(sd_journal_get_cursor(j, &k) >= 0);
+                printf("cursor: %s\n", k);
+                free(k);
+
+                assert_se(sd_journal_get_data(j, "MAGIC", &d, &l) >= 0);
+                printf("\t%.*s\n", (int) l, (const char*) d);
+
+                assert_se(sd_journal_get_data(j, "NUMBER", &d, &l) >= 0);
+                assert_se(k = strndup(d, l));
+                printf("\t%s\n", k);
+
+                if (skip > 0) {
+                        assert_se(safe_atou(k + 7, &u) >= 0);
+                        assert_se(i == u);
+                        i += skip;
+                }
+
+                free(k);
+        }
+
+        if (skip > 0)
+                assert_se(i == N_ENTRIES);
+}
+
+int main(int argc, char *argv[]) {
+        JournalFile *one, *two, *three;
+        char t[] = "/tmp/journal-stream-XXXXXX";
+        unsigned i;
+        sd_journal *j;
+        char *z;
+
+        log_set_max_level(LOG_DEBUG);
+
+        assert_se(mkdtemp(t));
+        assert_se(chdir(t) >= 0);
+
+        assert_se(journal_file_open("one.journal", O_RDWR|O_CREAT, 0666, NULL, &one) == 0);
+        assert_se(journal_file_open("two.journal", O_RDWR|O_CREAT, 0666, NULL, &two) == 0);
+        assert_se(journal_file_open("three.journal", O_RDWR|O_CREAT, 0666, NULL, &three) == 0);
+
+        for (i = 0; i < N_ENTRIES; i++) {
+                char *p, *q;
+                dual_timestamp ts;
+                struct iovec iovec[2];
+
+                dual_timestamp_get(&ts);
+
+                assert_se(asprintf(&p, "NUMBER=%u", i) >= 0);
+                iovec[0].iov_base = p;
+                iovec[0].iov_len = strlen(p);
+
+                assert_se(asprintf(&q, "MAGIC=%s", i % 5 == 0 ? "quux" : "waldo") >= 0);
+
+                iovec[1].iov_base = q;
+                iovec[1].iov_len = strlen(q);
+
+                if (i % 10 == 0)
+                        assert_se(journal_file_append_entry(three, &ts, iovec, 2, NULL, NULL, NULL) == 0);
+                else {
+                        if (i % 3 == 0)
+                                assert_se(journal_file_append_entry(two, &ts, iovec, 2, NULL, NULL, NULL) == 0);
+
+                        assert_se(journal_file_append_entry(one, &ts, iovec, 2, NULL, NULL, NULL) == 0);
+                }
+
+                free(p);
+                free(q);
+        }
+
+        journal_file_close(one);
+        journal_file_close(two);
+        journal_file_close(three);
+
+        assert_se(sd_journal_open_directory(&j, t, 0) >= 0);
+
+        assert_se(sd_journal_add_match(j, "MAGIC=quux", 0) >= 0);
+        SD_JOURNAL_FOREACH_BACKWARDS(j) {
+                const void *d;
+                size_t l;
+
+                assert_se(sd_journal_get_data(j, "NUMBER", &d, &l) >= 0);
+                printf("\t%.*s\n", (int) l, (const char*) d);
+        }
+
+        SD_JOURNAL_FOREACH(j) {
+                const void *d;
+                size_t l;
+
+                assert_se(sd_journal_get_data(j, "NUMBER", &d, &l) >= 0);
+                printf("\t%.*s\n", (int) l, (const char*) d);
+        }
+
+        sd_journal_flush_matches(j);
+
+        verify_contents(j, 1);
+
+        printf("NEXT TEST\n");
+        assert_se(sd_journal_add_match(j, "MAGIC=quux", 0) >= 0);
+
+        assert_se(z = journal_make_match_string(j));
+        printf("resulting match expression is: %s\n", z);
+        free(z);
+
+        verify_contents(j, 5);
+
+        printf("NEXT TEST\n");
+        sd_journal_flush_matches(j);
+        assert_se(sd_journal_add_match(j, "MAGIC=waldo", 0) >= 0);
+        assert_se(sd_journal_add_match(j, "NUMBER=10", 0) >= 0);
+        assert_se(sd_journal_add_match(j, "NUMBER=11", 0) >= 0);
+        assert_se(sd_journal_add_match(j, "NUMBER=12", 0) >= 0);
+
+        assert_se(z = journal_make_match_string(j));
+        printf("resulting match expression is: %s\n", z);
+        free(z);
+
+        verify_contents(j, 0);
+
+        sd_journal_close(j);
+
+        assert_se(rm_rf(t, false, true, false) >= 0);
+
+        return 0;
+}
diff --git a/src/systemd/sd-journal.h b/src/systemd/sd-journal.h
index ab968b9496..74e57f48e0 100644
--- a/src/systemd/sd-journal.h
+++ b/src/systemd/sd-journal.h
@@ -88,6 +88,7 @@ int sd_journal_enumerate_data(sd_journal *j, const void **data, size_t *l);
 void sd_journal_restart_data(sd_journal *j);
 
 int sd_journal_add_match(sd_journal *j, const void *data, size_t size);
+int sd_journal_add_disjunction(sd_journal *j);
 void sd_journal_flush_matches(sd_journal *j);
 
 int sd_journal_seek_head(sd_journal *j);