You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@httpd.apache.org by Brian Pane <bp...@pacbell.net> on 2001/09/04 01:45:31 UTC
[PATCH] pre-merge of per-dir configs to speed up directory_walk
This is an updated version of a patch that I posted a while back. I've
cleaned up my code a bit and modified it to work with the latest version
of mod_include.
This patch attempts to pre-merge all of the non-regex, non-.htaccess
per-directory configuration structures at server startup, so that
directory_walk can use the pre-merged values. The motivation for
this is to eliminate expensive dir_merge functions during request
processing.
Notes:
* The pre-merge logic depends on dir_merge functions respecting
the constness of the 'base' config that they're passed. If we
later need to support dir_merge functions that modify the base
in the 'same pool' case (like Bill Rowe was investigating for
mod_mime), it's possible to do so by giving each pre-merged
config its own pool.
* The comments in core.c describe the pre-merge algorithm and
the design tradeoffs that I selected.
Does anybody have time to review this code?
Thanks,
--Brian
[ Part 2: "Attached Text" ]
Index: include/http_core.h
===================================================================
RCS file: /home/cvspublic/httpd-2.0/include/http_core.h,v
retrieving revision 1.51
diff -u -r1.51 http_core.h
--- include/http_core.h 2001/08/30 05:10:53 1.51
+++ include/http_core.h 2001/09/03 23:19:34
@@ -488,6 +488,14 @@
char *access_name;
apr_array_header_t *sec_dir;
apr_array_header_t *sec_url;
+
+ /* Pre-merged per-dir configs */
+#define NUM_PRE_MERGE_DIRS 6
+ struct {
+ const char *dirname;
+ ap_conf_vector_t *conf;
+ } pre_merged_dir_conf[1 << NUM_PRE_MERGE_DIRS];
+
} core_server_config;
/* for http_config.c */
Index: server/core.c
===================================================================
RCS file: /home/cvspublic/httpd-2.0/server/core.c,v
retrieving revision 1.58
diff -u -r1.58 core.c
--- server/core.c 2001/08/31 13:45:16 1.58
+++ server/core.c 2001/09/03 23:19:36
@@ -3352,6 +3352,166 @@
ap_set_version(pconf);
}
+
+static int is_possible_predecessor(const char *dir1, const char *dir2)
+{
+ char c1, c2;
+ while ((c1 = *dir1++)) {
+ c2 = *dir2++;
+ if (c1 != c2) {
+ if ((c1 == '*') || (c2 == '*')) {
+ while ((c1 = *dir1) && (c1 != '/'))
+ dir1++;
+ while ((c2 = *dir2) && (c2 != '/'))
+ dir2++;
+ }
+ else {
+ return 0;
+ }
+ }
+ }
+ return 1;
+}
+
+
+/* Pre-merge the per-directory configurations, to avoid the
+ * overhead of doing this for each request (see directory_walk
+ * in request.c).
+ *
+ * Background:
+ *
+ * There are 'n' per-directory configurations. The ap_directory_walk()
+ * function (server/request.c) scans through them from i=0 through i=n-1
+ * and either merges 'per-dir-config[i]' into its pending request
+ * configuration or leaves that config out (depending on whether
+ * the directory name associated with per-dir-config[i] matches the
+ * requested URI or not).
+ *
+ * It's possible to represent the set of merges done for a request
+ * as a vector of bits, V[0] through V[n-1]. V[i] is 1 if
+ * per-dir-config[i] is used for the request, or 0 if it isn't.
+ * Conceptually, pre_merge_per_dir_configs() is responsible for
+ * pre-building the final per-dir configuration associated with
+ * each possible value of this bit vector. Given this pre-merged
+ * config structure, directory_walk() can just look up the
+ * end result instead of actually doing all of the merging at
+ * request time.
+ *
+ * In the general case, it's not feasible to precompute all
+ * permutations of V, because there are O(2^n) possibilities.
+ * Thus pre_merge_per_dir_configs() computes the pre-merge
+ * for the first NUM_PRE_MERGE_DIRS directories. It still
+ * uses O(2^m) storage, but m is constrained to a small value.
+ * As an additional space optimization, the function skips
+ * impossible permutations (e.g., if you have <Directory>
+ * blocks for "/news" and "/downloads/pc", their configs can't
+ * ever be merged).
+ */
+static void pre_merge_per_dir_configs(apr_pool_t *p, server_rec *s)
+{
+ core_server_config *sconf;
+ apr_array_header_t *sec;
+ int nelts;
+ ap_conf_vector_t **elts;
+ int num_bits;
+ int i;
+ int max;
+ int mask;
+ int threshold;
+ int j;
+
+ sconf = ap_get_module_config(s->module_config, &core_module);
+ sec = sconf->sec_dir;
+ nelts = sec->nelts;
+ elts = (ap_conf_vector_t **)sec->elts;
+
+ num_bits =
+ (sec->nelts < NUM_PRE_MERGE_DIRS) ? sec->nelts : NUM_PRE_MERGE_DIRS;
+ max = (1 << num_bits);
+
+ sconf->pre_merged_dir_conf[0].conf = s->lookup_defaults;
+ sconf->pre_merged_dir_conf[0].dirname = "";
+ mask = 1;
+ threshold = 2;
+ j = 0;
+ /* i holds the value of the bit vector 'V' in the
+ * algorithm described in the comments at the top
+ * of this function. To make the code simpler, the
+ * bits are 'backwards'; the low order bit of i is V[0].
+ * sconf->pre_merged_dir_conf is a vector of 2^NUM_PRE_MERGE_DIRS
+ * elements; for any permutation P of the bits in V,
+ * sconf->pre_merged_dir_conf[P] contains the merged
+ * per-dir configuration corresponding to P.
+ */
+ for (i = 1; i < max; i++) {
+ int parent;
+ if (i == threshold) {
+ mask = threshold;
+ threshold <<= 1;
+ j++;
+ }
+
+ /* The bit vector 'V' can be thought of as a tree;
+ * the configuration for a node is computed
+ * incrementally by merging with its parent
+ */
+ parent = i & (mask - 1);
+
+ if (sconf->pre_merged_dir_conf[parent].conf == NULL) {
+ /* If the parent node represents an unreachable
+ * state, so does the child, so don't bother
+ * computing it
+ */
+ continue;
+ }
+ if (i & mask) {
+ /* A 1 value in the new high-order bit corresponds to
+ * a permutation in which the j'th per-directory config
+ * is a match against the requested filename. Thus we
+ * should compute the merge of the j'th config with
+ * the config stored in the parent node. However,
+ * if the j'th config corresponds to a <Directory>
+ * path that can't possibly match a filename that
+ * matched the parent node, then we needn't waste
+ * time or memory computing it
+ */
+ core_dir_config *core_elt = ap_get_module_config(elts[j],
+ &core_module);
+ const char *dirname = core_elt->d;
+ const char *parent_dirname =
+ sconf->pre_merged_dir_conf[parent].dirname;
+ if (is_possible_predecessor(parent_dirname, dirname)) {
+ sconf->pre_merged_dir_conf[i].conf =
+ ap_merge_per_dir_configs(p,
+ sconf->pre_merged_dir_conf[parent].conf, elts[j]);
+ sconf->pre_merged_dir_conf[i].dirname = dirname;
+ }
+ }
+ else {
+ /* A 0 value in the new high-order bit corresponds to
+ * a permutation in which the j'th per-directory config
+ * is not matched. Thus the merged configuration for
+ * this node is the same as that for its parent, and
+ * we can copy the pointer rather than making another
+ * copy of the merged config
+ */
+ sconf->pre_merged_dir_conf[i] = sconf->pre_merged_dir_conf[parent];
+ }
+ }
+}
+
+static void core_post_config_merge(apr_pool_t *p, apr_pool_t *plog,
+ apr_pool_t *ptemp, server_rec *s)
+{
+ server_rec *virt;
+
+ for (virt = s->next; virt; virt = virt->next) {
+ pre_merge_per_dir_configs(p, virt);
+ }
+ pre_merge_per_dir_configs(p, s);
+}
+
+
static void core_open_logs(apr_pool_t *pconf, apr_pool_t *plog, apr_pool_t *ptemp, server_rec *s)
{
ap_open_logs(s, pconf);
@@ -3397,6 +3557,7 @@
static void register_hooks(apr_pool_t *p)
{
ap_hook_post_config(core_post_config,NULL,NULL,APR_HOOK_REALLY_FIRST);
+ ap_hook_post_config(core_post_config_merge,NULL,NULL,APR_HOOK_REALLY_LAST);
ap_hook_translate_name(ap_core_translate,NULL,NULL,APR_HOOK_REALLY_LAST);
ap_hook_map_to_storage(core_map_to_storage,NULL,NULL,APR_HOOK_REALLY_LAST);
ap_hook_open_logs(core_open_logs,NULL,NULL,APR_HOOK_MIDDLE);
Index: server/request.c
===================================================================
RCS file: /home/cvspublic/httpd-2.0/server/request.c,v
retrieving revision 1.48
diff -u -r1.48 request.c
--- server/request.c 2001/09/01 05:21:16 1.48
+++ server/request.c 2001/09/03 23:19:38
@@ -515,6 +515,7 @@
ap_conf_vector_t *per_dir_defaults = r->server->lookup_defaults;
ap_conf_vector_t **sec_dir = (ap_conf_vector_t **) sconf->sec_dir->elts;
int num_sec = sconf->sec_dir->nelts;
+ unsigned int bitmask = 0;
char *test_filename;
char *test_dirname;
int res;
@@ -699,9 +700,23 @@
this_conf = entry_config;
if (this_conf) {
- per_dir_defaults = ap_merge_per_dir_configs(r->pool,
- per_dir_defaults,
- this_conf);
+ /* See pre_merge_per_dir_configs in server/core.c for
+ * documentation on the pre-merge bitmap design
+ */
+ int pre_merged = 0;
+ if (j < NUM_PRE_MERGE_DIRS) {
+ bitmask |= (1 << j);
+ if (sconf->pre_merged_dir_conf[bitmask].conf) {
+ per_dir_defaults =
+ sconf->pre_merged_dir_conf[bitmask].conf;
+ pre_merged = 1;
+ }
+ }
+ if (!pre_merged) {
+ per_dir_defaults =
+ ap_merge_per_dir_configs(r->pool, per_dir_defaults,
+ this_conf);
+ }
core_dir = ap_get_module_config(per_dir_defaults,
&core_module);
}
@@ -793,6 +808,7 @@
int num_sec = sconf->sec_dir->nelts;
int sec_idx;
unsigned int seg, startseg;
+ unsigned int bitmask = 0;
int res;
ap_conf_vector_t *entry_config;
core_dir_config *entry_core;
@@ -871,6 +887,7 @@
*/
for (; sec_idx < num_sec; ++sec_idx) {
const char *entry_dir;
+ int pre_merged = 0;
entry_config = sec_ent[sec_idx];
entry_core = ap_get_module_config(entry_config, &core_module);
@@ -894,9 +911,22 @@
continue;
}
- per_dir_defaults = ap_merge_per_dir_configs(r->pool,
- per_dir_defaults,
- entry_config);
+ /* See pre_merge_per_dir_configs in server/core.c for
+ * documentation on the pre-merge bitmap design
+ */
+ if (sec_idx < NUM_PRE_MERGE_DIRS) {
+ bitmask |= (1 << sec_idx);
+ if (sconf->pre_merged_dir_conf[bitmask].conf) {
+ per_dir_defaults =
+ sconf->pre_merged_dir_conf[bitmask].conf;
+ pre_merged = 1;
+ }
+ }
+ if (!pre_merged) {
+ per_dir_defaults =
+ ap_merge_per_dir_configs(r->pool, per_dir_defaults,
+ entry_config);
+ }
core_dir = ap_get_module_config(per_dir_defaults,
&core_module);
}