From d052cff922c64d3f4105eef53d59075146eec438 Mon Sep 17 00:00:00 2001
From: Yann Ylavic <ylavic@apache.org>
Date: Thu, 14 May 2020 09:02:13 +0000
Subject: [PATCH] mod_proxy: binary search for ProxyErrorOverride status codes.

The list can be rather long, speed up runtime by sorting the status codes in
error_override_codes and using binary search from ap_proxy_should_override().


git-svn-id: https://svn.apache.org/repos/asf/httpd/httpd/trunk@1877728 13f79535-47bb-0310-9956-ffa450edef68
---
 modules/proxy/mod_proxy.c  | 27 ++++++++++++++++++++++++++-
 modules/proxy/proxy_util.c | 30 +++++++++++++++++++++---------
 2 files changed, 47 insertions(+), 10 deletions(-)

diff --git a/modules/proxy/mod_proxy.c b/modules/proxy/mod_proxy.c
index 057d34deec8..c0a44222c8a 100644
--- a/modules/proxy/mod_proxy.c
+++ b/modules/proxy/mod_proxy.c
@@ -1599,6 +1599,11 @@ static void *create_proxy_dir_config(apr_pool_t *p, char *dummy)
     return (void *) new;
 }
 
+static int int_order(const void *i1, const void *i2)
+{
+    return *(const int *)i1 - *(const int *)i2;
+}
+
 static void *merge_proxy_dir_config(apr_pool_t *p, void *basev, void *addv)
 {
     proxy_dir_conf *new = (proxy_dir_conf *) apr_pcalloc(p, sizeof(proxy_dir_conf));
@@ -1618,6 +1623,15 @@ static void *merge_proxy_dir_config(apr_pool_t *p, void *basev, void *addv)
         = apr_array_append(p, base->cookie_domains, add->cookie_domains);
     new->error_override_codes
         = apr_array_append(p, base->error_override_codes, add->error_override_codes);
+    /* Keep the array sorted for binary search (since "base" and "add" are
+     * already sorted, it's only needed only if both are merged).
+     */
+    if (base->error_override_codes->nelts
+            && add->error_override_codes->nelts) {
+        qsort(new->error_override_codes->elts,
+              new->error_override_codes->nelts,
+              sizeof(int), int_order);
+    }
     new->interpolate_env = (add->interpolate_env == -1) ? base->interpolate_env
                                                         : add->interpolate_env;
     new->preserve_host = (add->preserve_host_set == 0) ? base->preserve_host
@@ -2142,7 +2156,7 @@ static const char *
     }
     else if (conf->error_override_set == 1) {
         int *newcode;
-        int argcode;
+        int argcode, i;
         if (!apr_isdigit(arg[0]))
             return "ProxyErrorOverride: status codes to intercept must be numeric";
         if (!conf->error_override) 
@@ -2154,6 +2168,17 @@ static const char *
 
         newcode = apr_array_push(conf->error_override_codes);
         *newcode = argcode;
+
+        /* Keep the array sorted for binary search. */
+        for (i = conf->error_override_codes->nelts - 1; i > 0; --i) {
+            int *oldcode = &((int *)conf->error_override_codes->elts)[i - 1];
+            if (*oldcode <= argcode) {
+                break;
+            }
+            *newcode = *oldcode;
+            *oldcode = argcode;
+            newcode = oldcode;
+        }
     }
     else
         return "ProxyErrorOverride first parameter must be one of: off | on";
diff --git a/modules/proxy/proxy_util.c b/modules/proxy/proxy_util.c
index 5c9f93e7120..c0c19110b9b 100644
--- a/modules/proxy/proxy_util.c
+++ b/modules/proxy/proxy_util.c
@@ -3390,20 +3390,29 @@ int ap_proxy_lb_workers(void)
     return lb_workers_limit;
 }
 
-static int error_code_overridden(proxy_dir_conf *conf, int code)
+static APR_INLINE int error_code_overridden(const int *elts, int nelts,
+                                            int code)
 {
-    int i;
-    int *list = (int *) conf->error_override_codes->elts;
+    int min = 0;
+    int max = nelts - 1;
+    AP_DEBUG_ASSERT(max >= 0);
 
-    if (apr_is_empty_array(conf->error_override_codes))
-        return 0;
+    while (min < max) {
+        int mid = (min + max) / 2;
+        int val = elts[mid];
 
-    for (i = 0; i < conf->error_override_codes->nelts; i++) {
-        if (code == list[i])
+        if (val < code) {
+            min = mid + 1;
+        }
+        else if (val > code) {
+            max = mid - 1;
+        }
+        else {
             return 1;
+        }
     }
 
-    return 0;
+    return elts[min] == code;
 }
 
 PROXY_DECLARE(int) ap_proxy_should_override(proxy_dir_conf *conf, int code)
@@ -3414,7 +3423,10 @@ PROXY_DECLARE(int) ap_proxy_should_override(proxy_dir_conf *conf, int code)
     if (apr_is_empty_array(conf->error_override_codes))
         return ap_is_HTTP_ERROR(code);
 
-    return error_code_overridden(conf, code);
+    /* Since error_override_codes is sorted, apply binary search. */
+    return error_code_overridden((int *)conf->error_override_codes->elts,
+                                 conf->error_override_codes->nelts,
+                                 code);
 }
 
 /* deprecated - to be removed in v2.6 */
-- 
2.47.3