Add latest changes from gitlab-org/gitlab@master

9 files changed, 181 insertions, 65 deletions

diff --git a/app/models/namespaces/traversal/linear_scopes.rb b/app/models/namespaces/traversal/linear_scopes.rb
index 2da0e48c2da..f4dc69395c8 100644
--- a/app/models/namespaces/traversal/linear_scopes.rb
+++ b/app/models/namespaces/traversal/linear_scopes.rb
@@ -40,18 +40,24 @@ module Namespaces
         def self_and_descendants(include_self: true)
           return super unless use_traversal_ids?
 
-          records = self_and_descendants_with_duplicates(include_self: include_self)
-
-          distinct = records.select('DISTINCT on(namespaces.id) namespaces.*')
-
-          distinct.normal_select
+          if Feature.enabled?(:traversal_ids_btree, default_enabled: :yaml)
+            self_and_descendants_with_comparison_operators(include_self: include_self)
+          else
+            records = self_and_descendants_with_duplicates_with_array_operator(include_self: include_self)
+            distinct = records.select('DISTINCT on(namespaces.id) namespaces.*')
+            distinct.normal_select
+          end
         end
 
         def self_and_descendant_ids(include_self: true)
           return super unless use_traversal_ids?
 
-          self_and_descendants_with_duplicates(include_self: include_self)
-            .select('DISTINCT namespaces.id')
+          if Feature.enabled?(:traversal_ids_btree, default_enabled: :yaml)
+            self_and_descendants_with_comparison_operators(include_self: include_self).as_ids
+          else
+            self_and_descendants_with_duplicates_with_array_operator(include_self: include_self)
+              .select('DISTINCT namespaces.id')
+          end
         end
 
         # Make sure we drop the STI `type = 'Group'` condition for better performance.
@@ -89,7 +95,40 @@ module Namespaces
           use_traversal_ids?
         end
 
-        def self_and_descendants_with_duplicates(include_self: true)
+        def self_and_descendants_with_comparison_operators(include_self: true)
+          base = all.select(
+            :traversal_ids,
+            'LEAD (namespaces.traversal_ids, 1) OVER (ORDER BY namespaces.traversal_ids ASC) next_traversal_ids'
+          )
+          cte = Gitlab::SQL::CTE.new(:base_cte, base)
+
+          namespaces = Arel::Table.new(:namespaces)
+          records = unscoped
+            .without_sti_condition
+            .with(cte.to_arel)
+            .from([cte.table, namespaces])
+
+          # Bound the search space to ourselves (optional) and descendants.
+          #
+          # WHERE (base_cte.next_traversal_ids IS NULL OR base_cte.next_traversal_ids > namespaces.traversal_ids)
+          #   AND next_traversal_ids_sibling(base_cte.traversal_ids) > namespaces.traversal_ids
+          records = records
+            .where(cte.table[:next_traversal_ids].eq(nil).or(cte.table[:next_traversal_ids].gt(namespaces[:traversal_ids])))
+            .where(next_sibling_func(cte.table[:traversal_ids]).gt(namespaces[:traversal_ids]))
+
+          #   AND base_cte.traversal_ids <= namespaces.traversal_ids
+          if include_self
+            records.where(cte.table[:traversal_ids].lteq(namespaces[:traversal_ids]))
+          else
+            records.where(cte.table[:traversal_ids].lt(namespaces[:traversal_ids]))
+          end
+        end
+
+        def next_sibling_func(*args)
+          Arel::Nodes::NamedFunction.new('next_traversal_ids_sibling', args)
+        end
+
+        def self_and_descendants_with_duplicates_with_array_operator(include_self: true)
           base_ids = select(:id)
 
           records = unscoped
diff --git a/config/feature_flags/development/traversal_ids_btree.yml b/config/feature_flags/development/traversal_ids_btree.yml
new file mode 100644
index 00000000000..aaecafe04ae
--- /dev/null
+++ b/config/feature_flags/development/traversal_ids_btree.yml
@@ -0,0 +1,8 @@
+---
+name: traversal_ids_btree
+introduced_by_url: https://gitlab.com/gitlab-org/gitlab/-/merge_requests/69535
+rollout_issue_url: https://gitlab.com/gitlab-org/gitlab/-/issues/342871
+milestone: '14.5'
+type: development
+group: group::access
+default_enabled: false
diff --git a/db/migrate/20211012015903_next_traversal_ids_sibling_function.rb b/db/migrate/20211012015903_next_traversal_ids_sibling_function.rb
new file mode 100644
index 00000000000..f32b8fc5a65
--- /dev/null
+++ b/db/migrate/20211012015903_next_traversal_ids_sibling_function.rb
@@ -0,0 +1,30 @@
+# frozen_string_literal: true
+
+class NextTraversalIdsSiblingFunction < Gitlab::Database::Migration[1.0]
+  include Gitlab::Database::SchemaHelpers
+
+  FUNCTION_NAME = 'next_traversal_ids_sibling'
+
+  def up
+    # Given array [1,2,3,4,5], concatenate the first part of the array [1,2,3,4]
+    # with the last element in the array (5) after being incremented ([6]).
+    #
+    # [1,2,3,4,5] => [1,2,3,4,6]
+    execute(<<~SQL)
+      CREATE OR REPLACE FUNCTION #{FUNCTION_NAME}(traversal_ids INT[]) RETURNS INT[]
+      AS $$
+      BEGIN
+        return traversal_ids[1:array_length(traversal_ids, 1)-1] ||
+        ARRAY[traversal_ids[array_length(traversal_ids, 1)]+1];
+      END;
+      $$
+      LANGUAGE plpgsql
+      IMMUTABLE
+      RETURNS NULL ON NULL INPUT;
+    SQL
+  end
+
+  def down
+    execute("DROP FUNCTION #{FUNCTION_NAME}(traversal_ids INT[])")
+  end
+end
diff --git a/db/post_migrate/20211012051221_add_index_btree_namespaces_traversal_ids.rb b/db/post_migrate/20211012051221_add_index_btree_namespaces_traversal_ids.rb
new file mode 100644
index 00000000000..882351ab974
--- /dev/null
+++ b/db/post_migrate/20211012051221_add_index_btree_namespaces_traversal_ids.rb
@@ -0,0 +1,15 @@
+# frozen_string_literal: true
+
+class AddIndexBtreeNamespacesTraversalIds < Gitlab::Database::Migration[1.0]
+  INDEX_NAME = 'index_btree_namespaces_traversal_ids'
+
+  disable_ddl_transaction!
+
+  def up
+    add_concurrent_index :namespaces, :traversal_ids, using: :btree, name: INDEX_NAME
+  end
+
+  def down
+    remove_concurrent_index :namespaces, :traversal_ids, name: INDEX_NAME
+  end
+end
diff --git a/db/schema_migrations/20211012015903 b/db/schema_migrations/20211012015903
new file mode 100644
index 00000000000..bfa36780370
--- /dev/null
+++ b/db/schema_migrations/20211012015903
@@ -0,0 +1 @@
+4c3a55f7891dab4ee1ae019d97cf9d40e7bba81d87a544d6aa23a7f57e6d0f70
\ No newline at end of file
diff --git a/db/schema_migrations/20211012051221 b/db/schema_migrations/20211012051221
new file mode 100644
index 00000000000..0dc5e9331e1
--- /dev/null
+++ b/db/schema_migrations/20211012051221
@@ -0,0 +1 @@
+52b2a6d78fa649078167e842061ab7c04e3c41c0fc4a092a0a6123dad202fb0e
\ No newline at end of file
diff --git a/db/structure.sql b/db/structure.sql
index dba4015d044..fbadeae0377 100644
--- a/db/structure.sql
+++ b/db/structure.sql
@@ -46,6 +46,15 @@ RETURN NULL;
 END
 $$;
 
+CREATE FUNCTION next_traversal_ids_sibling(traversal_ids integer[]) RETURNS integer[]
+    LANGUAGE plpgsql IMMUTABLE STRICT
+    AS $$
+BEGIN
+  return traversal_ids[1:array_length(traversal_ids, 1)-1] ||
+  ARRAY[traversal_ids[array_length(traversal_ids, 1)]+1];
+END;
+$$;
+
 CREATE FUNCTION set_has_external_issue_tracker() RETURNS trigger
     LANGUAGE plpgsql
     AS $$
@@ -24512,6 +24521,8 @@ CREATE INDEX index_boards_on_project_id ON boards USING btree (project_id);
 
 CREATE INDEX index_broadcast_message_on_ends_at_and_broadcast_type_and_id ON broadcast_messages USING btree (ends_at, broadcast_type, id);
 
+CREATE INDEX index_btree_namespaces_traversal_ids ON namespaces USING btree (traversal_ids);
+
 CREATE INDEX index_bulk_import_configurations_on_bulk_import_id ON bulk_import_configurations USING btree (bulk_import_id);
 
 CREATE INDEX index_bulk_import_entities_on_bulk_import_id_and_status ON bulk_import_entities USING btree (bulk_import_id, status);
diff --git a/doc/administration/auth/ldap/index.md b/doc/administration/auth/ldap/index.md
index 92815f10b92..e3cba01fecf 100644
--- a/doc/administration/auth/ldap/index.md
+++ b/doc/administration/auth/ldap/index.md
@@ -19,50 +19,57 @@ This integration works with most LDAP-compliant directory servers, including:
 - Open LDAP.
 - 389 Server.
 
-Users added through LDAP take a [licensed seat](../../../subscriptions/self_managed/index.md#billable-users).
+Users added through LDAP:
 
-## Security
+- Take a [licensed seat](../../../subscriptions/self_managed/index.md#billable-users).
+- Can authenticate with Git using either their GitLab username or their email and LDAP password,
+  even if password authentication for Git 
+  [is disabled](../../../user/admin_area/settings/sign_in_restrictions.md#password-authentication-enabled).
 
-GitLab assumes that LDAP users:
+The LDAP DN is associated with existing GitLab users when:
 
-- Are not able to change their LDAP `mail`, `email`, or `userPrincipalName` attributes.
-  An LDAP user allowed to change their email on the LDAP server can potentially
-  [take over any account](#enable-ldap-sign-in-for-existing-gitlab-users)
-  on your GitLab server.
-- Have unique email addresses. If not, it's possible for LDAP users with the same
-  email address to share the same GitLab account.
+- The existing user signs in to GitLab with LDAP for the first time.
+- The LDAP email address is the primary email address of an existing GitLab user. If the LDAP email
+  attribute isn't found in the GitLab user database, a new user is created.
 
-We recommend against using LDAP integration if your LDAP users are
-allowed to change their `mail`, `email` or `userPrincipalName` attributes on
-the LDAP server, or share email addresses.
+If an existing GitLab user wants to enable LDAP sign-in for themselves, they should:
 
-### User deletion
+1. Check that their GitLab email address matches their LDAP email address.
+1. Sign in to GitLab by using their LDAP credentials.
 
-Users deleted from the LDAP server are immediately blocked from signing in
-to GitLab and [no longer consumes a
-license](../../../user/admin_area/moderate_users.md).
-However, there's an LDAP check cache time of one hour (which is
-[configurable](#adjust-ldap-user-sync-schedule) for GitLab Premium users).
-This means users already signed-in or who are using Git over SSH can access
-GitLab for up to one hour. Manually block the user in the GitLab Admin Area
-to immediately block all access.
+## Security risks
 
-## Git password authentication
+You should only use LDAP integration if your LDAP users cannot:
 
-LDAP-enabled users can authenticate with Git using their GitLab username or
-email and LDAP password, even if password authentication for Git is disabled
-in the application settings.
+- Change their `mail`, `email` or `userPrincipalName` attributes on the LDAP server. These
+  users can potentially take over any account on your GitLab server.
+- Share email addresses. LDAP users with the same email address can share the same GitLab
+  account.
 
-## Enable LDAP sign-in for existing GitLab users
+## Disable anonymous LDAP authentication
 
-When a user signs in to GitLab with LDAP for the first time and their LDAP
-email address is the primary email address of an existing GitLab user, the
-LDAP DN is associated with the existing user. If the LDAP email attribute
-isn't found in the GitLab user database, a new user is created.
+GitLab doesn't support TLS client authentication. Complete these steps on your LDAP server.
 
-In other words, if an existing GitLab user wants to enable LDAP sign-in for
-themselves, they should check that their GitLab email address matches their
-LDAP email address, and then sign into GitLab by using their LDAP credentials.
+1. Disable anonymous authentication.
+1. Enable one of the following authentication types:
+   - Simple authentication.
+   - Simple Authentication and Security Layer (SASL) authentication.
+
+The TLS client authentication setting in your LDAP server cannot be mandatory and clients cannot be
+authenticated with the TLS protocol.
+
+## Deleting users
+
+Users deleted from the LDAP server:
+
+- Are immediately blocked from signing in to GitLab.
+- [No longer consume a license](../../../user/admin_area/moderate_users.md).
+
+However, these users can continue to use Git with SSH until the next time the
+[LDAP check cache runs](#adjust-ldap-user-sync-schedule).
+
+To delete the account immediately, you can manually
+[block the user](../../../user/admin_area/moderate_users.md#block-a-user).
 
 ## Google Secure LDAP
 
@@ -170,7 +177,7 @@ These configuration settings are available:
 | `bind_dn`          | The full DN of the user you bind with. | **{dotted-circle}** No | `'america\momo'` or `'CN=Gitlab,OU=Users,DC=domain,DC=com'` |
 | `password`         | The password of the bind user. | **{dotted-circle}** No | `'your_great_password'` |
 | `encryption`       | Encryption method. The `method` key is deprecated in favor of `encryption`. | **{check-circle}** Yes | `'start_tls'` or `'simple_tls'` or `'plain'` |
-| `verify_certificates` | Enables SSL certificate verification if encryption method is `start_tls` or `simple_tls`. Defaults to true. | **{dotted-circle}** No | boolean |
+| `verify_certificates` | Enables SSL certificate verification if encryption method is `start_tls` or `simple_tls`. If set to false, no validation of the LDAP server's SSL certificate is performed. Defaults to true. | **{dotted-circle}** No | boolean |
 | `timeout`          | Set a timeout, in seconds, for LDAP queries. This helps avoid blocking a request if the LDAP server becomes unresponsive. A value of `0` means there is no timeout. (default: `10`) | **{dotted-circle}** No | `10` or `30` |
 | `active_directory` | This setting specifies if LDAP server is Active Directory LDAP server. For non-AD servers it skips the AD specific queries. If your LDAP server is not AD, set this to false. | **{dotted-circle}** No | boolean |
 | `allow_username_or_email_login` | If enabled, GitLab ignores everything after the first `@` in the LDAP username submitted by the user on sign-in. If you are using `uid: 'userPrincipalName'` on ActiveDirectory you must disable this setting, because the userPrincipalName contains an `@`. | **{dotted-circle}** No | boolean |
@@ -347,7 +354,7 @@ sync, while also allowing your SAML identity provider to handle additional
 checks like custom 2FA.
 
 When LDAP web sign in is disabled, users don't see an **LDAP** tab on the sign-in page.
-This does not disable [using LDAP credentials for Git access](#git-password-authentication).
+This does not disable using LDAP credentials for Git access.
 
 **Omnibus configuration**
 
@@ -458,26 +465,6 @@ If initially your LDAP configuration looked like:
 
 1. [Restart GitLab](../../restart_gitlab.md#installations-from-source) for the changes to take effect.
 
-## Encryption
-
-### TLS server authentication
-
-`simple_tls` and `start_tls` are the two available encryption methods.
-
-For either encryption method, if setting `verify_certificates: false`, TLS
-encryption is established with the LDAP server before any LDAP-protocol data is
-exchanged but no validation of the LDAP server's SSL certificate is performed.
-
-### Limitations
-
-#### TLS client authentication
-
-Not implemented by `Net::LDAP`.
-
-You should disable anonymous LDAP authentication and enable simple or Simple Authentication
-and Security Layer (SASL) authentication. The TLS client authentication setting in your LDAP server
-cannot be mandatory and clients cannot be authenticated with the TLS protocol.
-
 ## Multiple LDAP servers **(PREMIUM SELF)**
 
 With GitLab, you can configure multiple LDAP servers that your GitLab instance
diff --git a/spec/support/shared_examples/namespaces/traversal_scope_examples.rb b/spec/support/shared_examples/namespaces/traversal_scope_examples.rb
index 74b1bacc560..a315598b989 100644
--- a/spec/support/shared_examples/namespaces/traversal_scope_examples.rb
+++ b/spec/support/shared_examples/namespaces/traversal_scope_examples.rb
@@ -156,7 +156,7 @@ RSpec.shared_examples 'namespace traversal scopes' do
     end
   end
 
-  describe '.self_and_descendants' do
+  shared_examples '.self_and_descendants' do
     subject { described_class.where(id: [nested_group_1, nested_group_2]).self_and_descendants }
 
     it { is_expected.to contain_exactly(nested_group_1, deep_nested_group_1, nested_group_2, deep_nested_group_2) }
@@ -174,7 +174,19 @@ RSpec.shared_examples 'namespace traversal scopes' do
     end
   end
 
-  describe '.self_and_descendant_ids' do
+  describe '.self_and_descendants' do
+    include_examples '.self_and_descendants'
+
+    context 'with traversal_ids_btree feature flag disabled' do
+      before do
+        stub_feature_flags(traversal_ids_btree: false)
+      end
+
+      include_examples '.self_and_descendants'
+    end
+  end
+
+  shared_examples '.self_and_descendant_ids' do
     subject { described_class.where(id: [nested_group_1, nested_group_2]).self_and_descendant_ids.pluck(:id) }
 
     it { is_expected.to contain_exactly(nested_group_1.id, deep_nested_group_1.id, nested_group_2.id, deep_nested_group_2.id) }
@@ -190,4 +202,16 @@ RSpec.shared_examples 'namespace traversal scopes' do
       it { is_expected.to contain_exactly(deep_nested_group_1.id, deep_nested_group_2.id) }
     end
   end
+
+  describe '.self_and_descendant_ids' do
+    include_examples '.self_and_descendant_ids'
+
+    context 'with traversal_ids_btree feature flag disabled' do
+      before do
+        stub_feature_flags(traversal_ids_btree: false)
+      end
+
+      include_examples '.self_and_descendant_ids'
+    end
+  end
 end