New upstream version 1.40.0

12 files changed, 121 insertions, 38 deletions

diff --git a/docs/SUMMARY.md b/docs/SUMMARY.md
index db4ef1a4..10be12d6 100644
--- a/docs/SUMMARY.md
+++ b/docs/SUMMARY.md
@@ -67,7 +67,7 @@
 # Development
   - [Contributing Guide](development/contributing_guide.md)
   - [Code Style](code_style.md)
-  - [Git Usage](dev/git.md)
+  - [Git Usage](development/git.md)
   - [Testing]()
   - [OpenTracing](opentracing.md)
   - [Database Schemas](development/database_schema.md)
@@ -77,8 +77,9 @@
     - [TCP Replication](tcp_replication.md)
   - [Internal Documentation](development/internal_documentation/README.md)
     - [Single Sign-On]()
-      - [SAML](dev/saml.md)
-      - [CAS](dev/cas.md)
+      - [SAML](development/saml.md)
+      - [CAS](development/cas.md)
+    - [Room DAG concepts](development/room-dag-concepts.md)
     - [State Resolution]()
       - [The Auth Chain Difference Algorithm](auth_chain_difference_algorithm.md)
     - [Media Repository](media_repository.md)
diff --git a/docs/admin_api/user_admin_api.md b/docs/admin_api/user_admin_api.md
index 4a65d0c3..16089975 100644
--- a/docs/admin_api/user_admin_api.md
+++ b/docs/admin_api/user_admin_api.md
@@ -144,7 +144,8 @@ A response body like the following is returned:
             "deactivated": 0,
             "shadow_banned": 0,
             "displayname": "<User One>",
-            "avatar_url": null
+            "avatar_url": null,
+            "creation_ts": 1560432668000
         }, {
             "name": "<user_id2>",
             "is_guest": 0,
@@ -153,7 +154,8 @@ A response body like the following is returned:
             "deactivated": 0,
             "shadow_banned": 0,
             "displayname": "<User Two>",
-            "avatar_url": "<avatar_url>"
+            "avatar_url": "<avatar_url>",
+            "creation_ts": 1561550621000
         }
     ],
     "next_token": "100",
@@ -197,11 +199,12 @@ The following parameters should be set in the URL:
   - `shadow_banned` - Users are ordered by `shadow_banned` status.
   - `displayname` - Users are ordered alphabetically by `displayname`.
   - `avatar_url` - Users are ordered alphabetically by avatar URL.
+  - `creation_ts` - Users are ordered by when the users was created in ms.
 
 - `dir` - Direction of media order. Either `f` for forwards or `b` for backwards.
   Setting this value to `b` will reverse the above sort order. Defaults to `f`.
 
-Caution. The database only has indexes on the columns `name` and `created_ts`.
+Caution. The database only has indexes on the columns `name` and `creation_ts`.
 This means that if a different sort order is used (`is_guest`, `admin`,
 `user_type`, `deactivated`, `shadow_banned`, `avatar_url` or `displayname`),
 this can cause a large load on the database, especially for large environments.
@@ -222,6 +225,7 @@ The following fields are returned in the JSON response body:
   - `shadow_banned` - bool - Status if that user has been marked as shadow banned.
   - `displayname` - string - The user's display name if they have set one.
   - `avatar_url` - string -  The user's avatar URL if they have set one.
+  - `creation_ts` - integer - The user's creation timestamp in ms.
 
 - `next_token`: string representing a positive integer - Indication for pagination. See above.
 - `total` - integer - Total number of media.
diff --git a/docs/dev/cas.md b/docs/development/cas.md
index 592b2d8d..592b2d8d 100644
--- a/docs/dev/cas.md
+++ b/docs/development/cas.md
diff --git a/docs/dev/git.md b/docs/development/git.md
index 87950f07..9b1ed54b 100644
--- a/docs/dev/git.md
+++ b/docs/development/git.md
@@ -9,7 +9,7 @@ commits each of which contains a single change building on what came
 before. Here, by way of an arbitrary example, is the top of `git log --graph
 b2dba0607`:
 
-<img src="git/clean.png" alt="clean git graph" width="500px">
+<img src="img/git/clean.png" alt="clean git graph" width="500px">
 
 Note how the commit comment explains clearly what is changing and why. Also
 note the *absence* of merge commits, as well as the absence of commits called
@@ -61,7 +61,7 @@ Ok, so that's what we'd like to achieve. How do we achieve it?
 The TL;DR is: when you come to merge a pull request, you *probably* want to
 “squash and merge”:
 
-![squash and merge](git/squash.png).
+![squash and merge](img/git/squash.png).
 
 (This applies whether you are merging your own PR, or that of another
 contributor.)
@@ -105,7 +105,7 @@ complicated. Here's how we do it.
 
 Let's start with a picture:
 
-![branching model](git/branches.jpg)
+![branching model](img/git/branches.jpg)
 
 It looks complicated, but it's really not. There's one basic rule: *anyone* is
 free to merge from *any* more-stable branch to *any* less-stable branch at
diff --git a/docs/dev/git/branches.jpg b/docs/development/img/git/branches.jpg
index 715ecc8c..715ecc8c 100644
--- a/docs/dev/git/branches.jpg
+++ b/docs/development/img/git/branches.jpg
diff --git a/docs/dev/git/clean.png b/docs/development/img/git/clean.png
index 3accd7cc..3accd7cc 100644
--- a/docs/dev/git/clean.png
+++ b/docs/development/img/git/clean.png
diff --git a/docs/dev/git/squash.png b/docs/development/img/git/squash.png
index 234caca3..234caca3 100644
--- a/docs/dev/git/squash.png
+++ b/docs/development/img/git/squash.png
diff --git a/docs/development/room-dag-concepts.md b/docs/development/room-dag-concepts.md
new file mode 100644
index 00000000..5eed72be
--- /dev/null
+++ b/docs/development/room-dag-concepts.md
@@ -0,0 +1,79 @@
+# Room DAG concepts
+
+## Edges
+
+The word "edge" comes from graph theory lingo. An edge is just a connection
+between two events. In Synapse, we connect events by specifying their
+`prev_events`. A subsequent event points back at a previous event.
+
+```
+A (oldest) <---- B <---- C (most recent)
+```
+
+
+## Depth and stream ordering
+
+Events are normally sorted by `(topological_ordering, stream_ordering)` where
+`topological_ordering` is just `depth`. In other words, we first sort by `depth`
+and then tie-break based on `stream_ordering`. `depth` is incremented as new
+messages are added to the DAG. Normally, `stream_ordering` is an auto
+incrementing integer, but backfilled events start with `stream_ordering=-1` and decrement.
+
+---
+
+ - `/sync` returns things in the order they arrive at the server (`stream_ordering`).
+ - `/messages` (and `/backfill` in the federation API) return them in the order determined by the event graph `(topological_ordering, stream_ordering)`.
+
+The general idea is that, if you're following a room in real-time (i.e.
+`/sync`), you probably want to see the messages as they arrive at your server,
+rather than skipping any that arrived late; whereas if you're looking at a
+historical section of timeline (i.e. `/messages`), you want to see the best
+representation of the state of the room as others were seeing it at the time.
+
+
+## Forward extremity
+
+Most-recent-in-time events in the DAG which are not referenced by any other events' `prev_events` yet.
+
+The forward extremities of a room are used as the `prev_events` when the next event is sent.
+
+
+## Backwards extremity
+
+The current marker of where we have backfilled up to and will generally be the
+oldest-in-time events we know of in the DAG.
+
+This is an event where we haven't fetched all of the `prev_events` for.
+
+Once we have fetched all of its `prev_events`, it's unmarked as a backwards
+extremity (although we may have formed new backwards extremities from the prev
+events during the backfilling process).
+
+
+## Outliers
+
+We mark an event as an `outlier` when we haven't figured out the state for the
+room at that point in the DAG yet.
+
+We won't *necessarily* have the `prev_events` of an `outlier` in the database,
+but it's entirely possible that we *might*. The status of whether we have all of
+the `prev_events` is marked as a [backwards extremity](#backwards-extremity).
+
+For example, when we fetch the event auth chain or state for a given event, we
+mark all of those claimed auth events as outliers because we haven't done the
+state calculation ourself.
+
+
+## State groups
+
+For every non-outlier event we need to know the state at that event. Instead of
+storing the full state for each event in the DB (i.e. a `event_id -> state`
+mapping), which is *very* space inefficient when state doesn't change, we
+instead assign each different set of state a "state group" and then have
+mappings of `event_id -> state_group` and `state_group -> state`.
+
+
+### Stage group edges
+
+TODO: `state_group_edges` is a further optimization...
+      notes from @Azrenbeth, https://pastebin.com/seUGVGeT
diff --git a/docs/dev/saml.md b/docs/development/saml.md
index a9bfd2dc..a9bfd2dc 100644
--- a/docs/dev/saml.md
+++ b/docs/development/saml.md
diff --git a/docs/openid.md b/docs/openid.md
index cfaafc50..f685fd55 100644
--- a/docs/openid.md
+++ b/docs/openid.md
@@ -410,7 +410,7 @@ oidc_providers:
         display_name_template: "{{ user.name }}"
 ```
 
-## Apple
+### Apple
 
 Configuring "Sign in with Apple" (SiWA) requires an Apple Developer account.
 
diff --git a/docs/sample_config.yaml b/docs/sample_config.yaml
index 853c2f68..1a217f35 100644
--- a/docs/sample_config.yaml
+++ b/docs/sample_config.yaml
@@ -720,6 +720,9 @@ caches:
 # 'name' gives the database engine to use: either 'sqlite3' (for SQLite) or
 # 'psycopg2' (for PostgreSQL).
 #
+# 'txn_limit' gives the maximum number of transactions to run per connection
+# before reconnecting. Defaults to 0, which means no limit.
+#
 # 'args' gives options which are passed through to the database engine,
 # except for options starting 'cp_', which are used to configure the Twisted
 # connection pool. For a reference to valid arguments, see:
@@ -740,6 +743,7 @@ caches:
 #
 #database:
 #  name: psycopg2
+#  txn_limit: 10000
 #  args:
 #    user: synapse_user
 #    password: secretpassword
diff --git a/docs/upgrade.md b/docs/upgrade.md
index c8f4a2c1..ce9167e6 100644
--- a/docs/upgrade.md
+++ b/docs/upgrade.md
@@ -142,9 +142,9 @@ SQLite databases are unaffected by this change.
 
 The current spam checker interface is deprecated in favour of a new generic modules system.
 Authors of spam checker modules can refer to [this
-documentation](https://matrix-org.github.io/synapse/develop/modules.html#porting-an-existing-module-that-uses-the-old-interface)
+documentation](modules.md#porting-an-existing-module-that-uses-the-old-interface)
 to update their modules. Synapse administrators can refer to [this
-documentation](https://matrix-org.github.io/synapse/develop/modules.html#using-modules)
+documentation](modules.md#using-modules)
 to update their configuration once the modules they are using have been updated.
 
 We plan to remove support for the current spam checker interface in August 2021.
@@ -217,8 +217,7 @@ Instructions for doing so are provided
 
 ## Dropping support for old Python, Postgres and SQLite versions
 
-In line with our [deprecation
-policy](https://github.com/matrix-org/synapse/blob/release-v1.32.0/docs/deprecation_policy.md),
+In line with our [deprecation policy](deprecation_policy.md),
 we've dropped support for Python 3.5 and PostgreSQL 9.5, as they are no
 longer supported upstream.
 
@@ -231,8 +230,7 @@ The deprecated v1 "list accounts" admin API
 (`GET /_synapse/admin/v1/users/<user_id>`) has been removed in this
 version.
 
-The [v2 list accounts
-API](https://github.com/matrix-org/synapse/blob/master/docs/admin_api/user_admin_api.rst#list-accounts)
+The [v2 list accounts API](admin_api/user_admin_api.md#list-accounts)
 has been available since Synapse 1.7.0 (2019-12-13), and is accessible
 under `GET /_synapse/admin/v2/users`.
 
@@ -267,7 +265,7 @@ by the client.
 
 Synapse also requires the [Host]{.title-ref} header to be preserved.
 
-See the [reverse proxy documentation](../reverse_proxy.md), where the
+See the [reverse proxy documentation](reverse_proxy.md), where the
 example configurations have been updated to show how to set these
 headers.
 
@@ -286,7 +284,7 @@ identity providers:
     `[synapse public baseurl]/_synapse/client/oidc/callback` to the list
     of permitted "redirect URIs" at the identity provider.
 
-    See the [OpenID docs](../openid.md) for more information on setting
+    See the [OpenID docs](openid.md) for more information on setting
     up OpenID Connect.
 
 -   If your server is configured for single sign-on via a SAML2 identity
@@ -486,8 +484,7 @@ lock down external access to the Admin API endpoints.
 This release deprecates use of the `structured: true` logging
 configuration for structured logging. If your logging configuration
 contains `structured: true` then it should be modified based on the
-[structured logging
-documentation](../structured_logging.md).
+[structured logging documentation](structured_logging.md).
 
 The `structured` and `drains` logging options are now deprecated and
 should be replaced by standard logging configuration of `handlers` and
@@ -517,14 +514,13 @@ acts the same as the `http_client` argument previously passed to
 
 ## Forwarding `/_synapse/client` through your reverse proxy
 
-The [reverse proxy
-documentation](https://github.com/matrix-org/synapse/blob/develop/docs/reverse_proxy.md)
+The [reverse proxy documentation](reverse_proxy.md)
 has been updated to include reverse proxy directives for
 `/_synapse/client/*` endpoints. As the user password reset flow now uses
 endpoints under this prefix, **you must update your reverse proxy
 configurations for user password reset to work**.
 
-Additionally, note that the [Synapse worker documentation](https://github.com/matrix-org/synapse/blob/develop/docs/workers.md) has been updated to
+Additionally, note that the [Synapse worker documentation](workers.md) has been updated to
 
 :   state that the `/_synapse/client/password_reset/email/submit_token`
     endpoint can be handled
@@ -588,7 +584,7 @@ updated.
 When setting up worker processes, we now recommend the use of a Redis
 server for replication. **The old direct TCP connection method is
 deprecated and will be removed in a future release.** See
-[workers](../workers.md) for more details.
+[workers](workers.md) for more details.
 
 # Upgrading to v1.14.0
 
@@ -720,8 +716,7 @@ participating in many rooms.
     omitting the `CONCURRENTLY` keyword. Note however that this
     operation may in itself cause Synapse to stop running for some time.
     Synapse admins are reminded that [SQLite is not recommended for use
-    outside a test
-    environment](https://github.com/matrix-org/synapse/blob/master/README.rst#using-postgresql).
+    outside a test environment](postgres.md).
 
 3.  Once the index has been created, the `SELECT` query in step 1 above
     should complete quickly. It is therefore safe to upgrade to Synapse
@@ -739,7 +734,7 @@ participating in many rooms.
 Synapse will now log a warning on start up if used with a PostgreSQL
 database that has a non-recommended locale set.
 
-See [Postgres](../postgres.md) for details.
+See [Postgres](postgres.md) for details.
 
 # Upgrading to v1.8.0
 
@@ -856,8 +851,8 @@ section headed `email`, and be sure to have at least the
 You may also need to set `smtp_user`, `smtp_pass`, and
 `require_transport_security`.
 
-See the [sample configuration file](docs/sample_config.yaml) for more
-details on these settings.
+See the [sample configuration file](usage/configuration/homeserver_sample_config.md)
+for more details on these settings.
 
 #### Delegate email to an identity server
 
@@ -959,7 +954,7 @@ back to v1.3.1, subject to the following:
 
 Some counter metrics have been renamed, with the old names deprecated.
 See [the metrics
-documentation](../metrics-howto.md#renaming-of-metrics--deprecation-of-old-names-in-12)
+documentation](metrics-howto.md#renaming-of-metrics--deprecation-of-old-names-in-12)
 for details.
 
 # Upgrading to v1.1.0
@@ -995,7 +990,7 @@ more details on upgrading your database.
 Synapse v1.0 is the first release to enforce validation of TLS
 certificates for the federation API. It is therefore essential that your
 certificates are correctly configured. See the
-[FAQ](../MSC1711_certificates_FAQ.md) for more information.
+[FAQ](MSC1711_certificates_FAQ.md) for more information.
 
 Note, v1.0 installations will also no longer be able to federate with
 servers that have not correctly configured their certificates.
@@ -1010,8 +1005,8 @@ ways:-
 -   Configure a whitelist of server domains to trust via
     `federation_certificate_verification_whitelist`.
 
-See the [sample configuration file](docs/sample_config.yaml) for more
-details on these settings.
+See the [sample configuration file](usage/configuration/homeserver_sample_config.md)
+for more details on these settings.
 
 ## Email
 
@@ -1036,8 +1031,8 @@ If you are absolutely certain that you wish to continue using an
 identity server for password resets, set
 `trust_identity_server_for_password_resets` to `true`.
 
-See the [sample configuration file](docs/sample_config.yaml) for more
-details on these settings.
+See the [sample configuration file](usage/configuration/homeserver_sample_config.md)
+for more details on these settings.
 
 ## New email templates
 
@@ -1057,11 +1052,11 @@ sent to them.
 
 Please be aware that, before Synapse v1.0 is released around March 2019,
 you will need to replace any self-signed certificates with those
-verified by a root CA. Information on how to do so can be found at [the
-ACME docs](../ACME.md).
+verified by a root CA. Information on how to do so can be found at the
+ACME docs.
 
 For more information on configuring TLS certificates see the
-[FAQ](../MSC1711_certificates_FAQ.md).
+[FAQ](MSC1711_certificates_FAQ.md).
 
 # Upgrading to v0.34.0