httpd-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Dean Gaudet <dgau...@arctic.org>
Subject [PATCH] ap_overlap_tables
Date Mon, 10 Aug 1998 07:01:24 GMT
This isn't done.  It breaks "Set-Cookie"... stupid broken browsers. 
Set-Cookie can't be merged.  But that means that ap_overlap_tables can't
be used on r->err_headers_out, because it'll cause everything to be merged
(including previously unmerged entries). 

One solution is r->set_cookies or some crap like that. 

I dunno.  I'm off to bed. 

Dean

Index: include/alloc.h
===================================================================
RCS file: /export/home/cvs/apache-1.3/src/include/alloc.h,v
retrieving revision 1.62
diff -u -r1.62 alloc.h
--- alloc.h	1998/08/09 17:36:24	1.62
+++ alloc.h	1998/08/10 06:54:06
@@ -199,7 +199,7 @@
     int i;
 
     for (i = 0; i < barr->nelts; ++i) {
-	if (merge) {
+	if (flags & AP_OVERLAP_TABLES_MERGE) {
 	    ap_table_mergen(a, belt[i].key, belt[i].val);
 	}
 	else {
@@ -214,7 +214,9 @@
     in an ancestor of a's pool.  In practice b and a are usually from
     the same pool.
 */
-API_EXPORT(void) ap_overlap_tables(table *a, const table *b, int merge);
+#define AP_OVERLAP_TABLES_SET	(0)
+#define AP_OVERLAP_TABLES_MERGE	(1)
+API_EXPORT(void) ap_overlap_tables(table *a, const table *b, unsigned flags);
 
 /* XXX: these know about the definition of struct table in alloc.c.  That
  * definition is not here because it is supposed to be private, and by not
Index: main/alloc.c
===================================================================
RCS file: /export/home/cvs/apache-1.3/src/main/alloc.c,v
retrieving revision 1.98
diff -u -r1.98 alloc.c
--- alloc.c	1998/08/03 09:14:51	1.98
+++ alloc.c	1998/08/10 06:54:07
@@ -1386,6 +1386,163 @@
     va_end(vp);
 }
 
+/* Curse libc and the fact that it doesn't guarantee a stable sort.  We
+ * have to enforce stability ourselves by using the order field.  If it
+ * provided a stable sort then we wouldn't even need temporary storage to
+ * do the work below. -djg
+ *
+ * ("stable sort" means that equal keys retain their original relative
+ * ordering in the output.)
+ */
+typedef struct {
+    char *key;
+    char *val;
+    int order;
+} overlap_key;
+
+static int sort_overlap(const void *va, const void *vb)
+{
+    const overlap_key *a = va;
+    const overlap_key *b = vb;
+    int r;
+
+    r = strcasecmp(a->key, b->key);
+    if (r) {
+	return r;
+    }
+    return a->order - b->order;
+}
+
+/* prefer to use the stack for temp storage for overlaps smaller than this */
+#ifndef AP_OVERLAP_TABLES_ON_STACK
+#define AP_OVERLAP_TABLES_ON_STACK	(512)
+#endif
+
+API_EXPORT(void) ap_overlap_tables(table *a, const table *b, unsigned flags)
+{
+    overlap_key cat_keys_buf[AP_OVERLAP_TABLES_ON_STACK];
+    overlap_key *cat_keys;
+    int nkeys;
+    table_entry *e;
+    table_entry *last_e;
+    overlap_key *left;
+    overlap_key *right;
+    overlap_key *last;
+
+    nkeys = a->a.nelts + b->a.nelts;
+    if (nkeys < AP_OVERLAP_TABLES_ON_STACK) {
+	cat_keys = cat_keys_buf;
+    }
+    else {
+	/* XXX: could use scratch free space in a or b's pool instead...
+	 * which could save an allocation in b's pool.
+	 */
+	cat_keys = ap_palloc(b->a.pool, sizeof(overlap_key) * nkeys);
+    }
+
+    nkeys = 0;
+
+    /* Create a list of the entries from a concatenated with the entries
+     * from b.
+     */
+    e = (table_entry *)a->a.elts;
+    last_e = e + a->a.nelts;
+    while (e < last_e) {
+	cat_keys[nkeys].key = e->key;
+	cat_keys[nkeys].val = e->val;
+	cat_keys[nkeys].order = nkeys;
+	++nkeys;
+	++e;
+    }
+
+    e = (table_entry *)b->a.elts;
+    last_e = e + b->a.nelts;
+    while (e < last_e) {
+	cat_keys[nkeys].key = e->key;
+	cat_keys[nkeys].val = e->val;
+	cat_keys[nkeys].order = nkeys;
+	++nkeys;
+	++e;
+    }
+
+    qsort(cat_keys, nkeys, sizeof(overlap_key), sort_overlap);
+
+    /* Now iterate over the sorted list and rebuild a.
+     * Start by making sure it has enough space.
+     */
+    a->a.nelts = 0;
+    if (a->a.nalloc < nkeys) {
+	a->a.elts = ap_palloc(a->a.pool, a->a.elt_size * nkeys * 2);
+	a->a.nalloc = nkeys * 2;
+    }
+
+    /*
+     * In both the merge and set cases we retain the invariant:
+     *
+     * left->key, (left+1)->key, (left+2)->key, ..., (right-1)->key
+     * are all equal keys.  (i.e. strcasecmp returns 0)
+     *
+     * We essentially need to find the maximal
+     * right for each key, then we can do a quick merge or set as
+     * appropriate.
+     */
+
+    if (flags & AP_OVERLAP_TABLES_MERGE) {
+	left = cat_keys;
+	last = left + nkeys;
+	while (left < last) {
+	    right = left + 1;
+	    if (right == last
+		|| strcasecmp(left->key, right->key)) {
+		ap_table_addn(a, left->key, left->val);
+		left = right;
+	    }
+	    else {
+		char *strp;
+		char *value;
+		size_t len;
+
+		/* Have to merge some headers.  Let's re-use the order field,
+		 * since it's handy... we'll store the length of val there.
+		 */
+		left->order = strlen(left->val);
+		len = left->order;
+		do {
+		    right->order = strlen(right->val);
+		    len += 2 + right->order;
+		    ++right;
+		} while (right < last
+			&& !strcasecmp(left->key, right->key));
+		/* right points one past the last header to merge */
+		value = ap_palloc(a->a.pool, len + 1);
+		strp = value;
+		for (;;) {
+		    memcpy(strp, left->val, left->order);
+		    strp += left->order;
+		    ++left;
+		    if (left == right) break;
+		    *strp++ = ',';
+		    *strp++ = ' ';
+		}
+		*strp = 0;
+		ap_table_addn(a, (left-1)->key, value);
+	    }
+	}
+    }
+    else {
+	left = cat_keys;
+	last = left + nkeys;
+	while (left < last) {
+	    right = left + 1;
+	    while (right < last && !strcasecmp(left->key, right->key)) {
+		++right;
+	    }
+	    ap_table_addn(a, (right-1)->key, (right-1)->val);
+	    left = right;
+	}
+    }
+}
+
 /*****************************************************************
  *
  * Managing generic cleanups.  
Index: main/http_protocol.c
===================================================================
RCS file: /export/home/cvs/apache-1.3/src/main/http_protocol.c,v
retrieving revision 1.236
diff -u -r1.236 http_protocol.c
--- http_protocol.c	1998/08/10 04:16:15	1.236
+++ http_protocol.c	1998/08/10 06:54:07
@@ -713,77 +713,18 @@
     return 1;
 }
 
-/* Curse libc and the fact that it doesn't guarantee a stable sort.  We
- * have to enforce stability ourselves by using the order field. -djg
- */
-typedef struct {
-    char *key;
-    char *val;
-    unsigned order;
-} mime_key;
-
-static int sort_mime_headers(const void *va, const void *vb)
-{
-    const mime_key *a = va;
-    const mime_key *b = vb;
-    int r;
-
-    r = strcasecmp(a->key, b->key);
-    if (r) {
-	return r;
-    }
-    return (signed)a->order - (signed)b->order;
-}
-
-/* XXX: could use ap_overlap_tables here... which generalizes this code */
 static void get_mime_headers(request_rec *r)
 {
     char field[AP_LIMIT_REQUEST_FIELDSIZE + 2];  /* getline needs two extra */
     conn_rec *c = r->connection;
     char *value;
     char *copy;
-    pool *tmp;
-    array_header *arr;
-    mime_key *new_key;
-    mime_key *first;
-    mime_key *last;
-    mime_key *end;
-    char *strp;
-    unsigned order;
     int len;
     unsigned int fields_read = 0;
+    table *tmp_headers;
 
-    /* The array will store the headers in a way that we can merge them
-     * later in O(n*lg(n))... rather than deal with various O(n^2)
-     * operations.
-     */
-    tmp = ap_make_sub_pool(r->pool);
-    arr = ap_make_array(tmp, 50, sizeof(mime_key));
-    order = 0;
-
-    /* If headers_in is non-empty (i.e. we're parsing a trailer) then
-     * we have to merge.  Have I mentioned that I think this is a lame part
-     * of the HTTP standard?  Anyhow, we'll cheat, and just pre-seed our
-     * array with the existing headers... and take advantage of the much
-     * faster merging here. -djg
-     */
-    if (!ap_is_empty_table(r->headers_in)) {
-	array_header *t_arr;
-	table_entry *t;
-	table_entry *t_end;
-
-	t_arr = ap_table_elts(r->headers_in);
-	t = (table_entry *)t_arr->elts;
-	t_end = t + t_arr->nelts;
-	while (t < t_end) {
-	    new_key = ap_push_array(arr);
-	    new_key->order = order++;
-	    new_key->key = t->key;
-	    new_key->val = t->val;
-	    ++t;
-	}
-	ap_clear_table(r->headers_in);
-    }
+    /* We'll use ap_overlap_tables later to merge these into r->headers_in. */
+    tmp_headers = ap_make_table(r->pool, 50);
 
     /*
      * Read header lines until we get the empty separator line, a read error,
@@ -795,7 +736,6 @@
             r->status = HTTP_BAD_REQUEST;
             ap_table_setn(r->notes, "error-notes",
                 "Number of request header fields exceeds server limit.<P>\n");
-            ap_destroy_pool(tmp);
             return;
         }
         /* getline returns (size of max buffer - 1) if it fills up the
@@ -807,7 +747,6 @@
             ap_table_setn(r->notes, "error-notes", ap_pstrcat(r->pool,
                 "Size of a request header field exceeds server limit.<P>\n"
                 "<PRE>\n", field, "</PRE>\n", NULL));
-            ap_destroy_pool(tmp);
             return;
         }
         copy = ap_palloc(r->pool, len + 1);
@@ -818,7 +757,6 @@
             ap_table_setn(r->notes, "error-notes", ap_pstrcat(r->pool,
                 "Request header field is missing colon separator.<P>\n"
                 "<PRE>\n", copy, "</PRE>\n", NULL));
-            ap_destroy_pool(tmp);
             return;
         }
 
@@ -829,60 +767,10 @@
 
         /* XXX: should strip trailing whitespace as well */
 
-	/* Notice that key and val are actually in r->pool... this is a slight
-	 * optimization to handle the normal case, where we don't have twits
-	 * trying to exploit the server.  In the abnormal case where twits are
-	 * trying to exploit the server by causing it to do header merging
-	 * and other such nonsense we consume twice as much memory as we
-	 * could optimally.  Oh well.  -djg
-	 */
-	new_key = ap_push_array(arr);
-	new_key->order = order++;
-	new_key->key = copy;
-	new_key->val = value;
+	ap_table_addn(tmp_headers, copy, value);
     }
 
-    /* Now we have to merge headers. */
-    qsort(arr->elts, arr->nelts, sizeof(mime_key), sort_mime_headers);
-
-    /* Now iterate over the array and build r->headers_in. */
-    first = (mime_key *)arr->elts;
-    end = first + arr->nelts;
-    while (first < end) {
-	last = first + 1;
-	if (last == end
-	    || strcasecmp(first->key, last->key)) {
-	    ap_table_addn(r->headers_in, first->key, first->val);
-	    first = last;
-	}
-	else {
-	    /* Have to merge some headers.  Let's re-use the order field,
-	     * since it's handy... we'll store the length of val there.
-	     */
-	    first->order = strlen(first->val);
-	    len = first->order;
-	    do {
-		last->order = strlen(last->val);
-		len += 2 + last->order;
-		++last;
-	    } while (last < end
-		    && !strcasecmp(first->key, last->key));
-	    /* last points one past the last header to merge */
-	    value = ap_palloc(r->pool, len + 1);
-	    strp = value;
-	    for (;;) {
-		memcpy(strp, first->val, first->order);
-		strp += first->order;
-		++first;
-		if (first == last) break;
-		*strp++ = ',';
-		*strp++ = ' ';
-	    }
-	    *strp = 0;
-	    ap_table_addn(r->headers_in, (first-1)->key, value);
-	}
-    }
-    ap_destroy_pool(tmp);
+    ap_overlap_tables(r->headers_in, tmp_headers, AP_OVERLAP_TABLES_MERGE);
 }
 
 request_rec *ap_read_request(conn_rec *conn)
Index: main/util_script.c
===================================================================
RCS file: /export/home/cvs/apache-1.3/src/main/util_script.c,v
retrieving revision 1.128
diff -u -r1.128 util_script.c
--- util_script.c	1998/08/09 17:36:26	1.128
+++ util_script.c	1998/08/10 06:54:07
@@ -188,10 +188,9 @@
     return env;
 }
 
-/* XXX: this could use ap_overlap_tables */
 API_EXPORT(void) ap_add_common_vars(request_rec *r)
 {
-    table *e = r->subprocess_env;
+    table *e;
     server_rec *s = r->server;
     conn_rec *c = r->connection;
     const char *rem_logname;
@@ -200,11 +199,15 @@
     char *env_temp;
 #endif
     const char *host;
-
     array_header *hdrs_arr = ap_table_elts(r->headers_in);
     table_entry *hdrs = (table_entry *) hdrs_arr->elts;
     int i;
 
+    /* use a temporary table which we'll overlap onto
+     * r->subprocess_env later
+     */
+    e = ap_make_table(r->pool, 25 + hdrs_arr->nelts);
+
     /* First, add environment vars from headers... this is as per
      * CGI specs, though other sorts of scripting interfaces see
      * the same vars...
@@ -221,10 +224,10 @@
 	 */
 
 	if (!strcasecmp(hdrs[i].key, "Content-type")) {
-	    ap_table_setn(e, "CONTENT_TYPE", hdrs[i].val);
+	    ap_table_addn(e, "CONTENT_TYPE", hdrs[i].val);
 	}
 	else if (!strcasecmp(hdrs[i].key, "Content-length")) {
-	    ap_table_setn(e, "CONTENT_LENGTH", hdrs[i].val);
+	    ap_table_addn(e, "CONTENT_LENGTH", hdrs[i].val);
 	}
 	/*
 	 * You really don't want to disable this check, since it leaves you
@@ -238,7 +241,7 @@
 	}
 #endif
 	else {
-	    ap_table_setn(e, http2env(r->pool, hdrs[i].key), hdrs[i].val);
+	    ap_table_addn(e, http2env(r->pool, hdrs[i].key), hdrs[i].val);
 	}
     }
 
@@ -248,54 +251,56 @@
 
 #ifdef WIN32
     if (env_temp = getenv("SystemRoot")) {
-        ap_table_setn(e, "SystemRoot", env_temp);         
+        ap_table_addn(e, "SystemRoot", env_temp);         
     }
     if (env_temp = getenv("COMSPEC")) {
-        ap_table_setn(e, "COMSPEC", env_temp);            
+        ap_table_addn(e, "COMSPEC", env_temp);            
     }
     if (env_temp = getenv("WINDIR")) {
-        ap_table_setn(e, "WINDIR", env_temp);
+        ap_table_addn(e, "WINDIR", env_temp);
     }
 #endif
 
-    ap_table_setn(e, "PATH", env_path);
-    ap_table_setn(e, "SERVER_SOFTWARE", ap_get_server_version());
-    ap_table_setn(e, "SERVER_NAME", ap_get_server_name(r));
-    ap_table_setn(e, "SERVER_PORT",
+    ap_table_addn(e, "PATH", env_path);
+    ap_table_addn(e, "SERVER_SOFTWARE", ap_get_server_version());
+    ap_table_addn(e, "SERVER_NAME", ap_get_server_name(r));
+    ap_table_addn(e, "SERVER_PORT",
 		  ap_psprintf(r->pool, "%u", ap_get_server_port(r)));
     host = ap_get_remote_host(c, r->per_dir_config, REMOTE_HOST);
     if (host) {
-	ap_table_setn(e, "REMOTE_HOST", host);
+	ap_table_addn(e, "REMOTE_HOST", host);
     }
-    ap_table_setn(e, "REMOTE_ADDR", c->remote_ip);
-    ap_table_setn(e, "DOCUMENT_ROOT", ap_document_root(r));	/* Apache */
-    ap_table_setn(e, "SERVER_ADMIN", s->server_admin);	/* Apache */
-    ap_table_setn(e, "SCRIPT_FILENAME", r->filename);	/* Apache */
+    ap_table_addn(e, "REMOTE_ADDR", c->remote_ip);
+    ap_table_addn(e, "DOCUMENT_ROOT", ap_document_root(r));	/* Apache */
+    ap_table_addn(e, "SERVER_ADMIN", s->server_admin);	/* Apache */
+    ap_table_addn(e, "SCRIPT_FILENAME", r->filename);	/* Apache */
 
-    ap_table_setn(e, "REMOTE_PORT",
+    ap_table_addn(e, "REMOTE_PORT",
 		  ap_psprintf(r->pool, "%d", ntohs(c->remote_addr.sin_port)));
 
     if (c->user) {
-	ap_table_setn(e, "REMOTE_USER", c->user);
+	ap_table_addn(e, "REMOTE_USER", c->user);
     }
     if (c->ap_auth_type) {
-	ap_table_setn(e, "AUTH_TYPE", c->ap_auth_type);
+	ap_table_addn(e, "AUTH_TYPE", c->ap_auth_type);
     }
     rem_logname = ap_get_remote_logname(r);
     if (rem_logname) {
-	ap_table_setn(e, "REMOTE_IDENT", ap_pstrdup(r->pool, rem_logname));
+	ap_table_addn(e, "REMOTE_IDENT", ap_pstrdup(r->pool, rem_logname));
     }
 
     /* Apache custom error responses. If we have redirected set two new vars */
 
     if (r->prev) {
         if (r->prev->args) {
-	    ap_table_setn(e, "REDIRECT_QUERY_STRING", r->prev->args);
+	    ap_table_addn(e, "REDIRECT_QUERY_STRING", r->prev->args);
 	}
 	if (r->prev->uri) {
-	    ap_table_setn(e, "REDIRECT_URL", r->prev->uri);
+	    ap_table_addn(e, "REDIRECT_URL", r->prev->uri);
 	}
     }
+
+    ap_overlap_tables(r->subprocess_env, e, AP_OVERLAP_TABLES_SET);
 }
 
 /* This "cute" little function comes about because the path info on
@@ -419,6 +424,7 @@
     char *w, *l;
     int p;
     int cgi_status = HTTP_OK;
+    table *merge;
 
     if (buffer) {
 	*buffer = '\0';
@@ -427,6 +433,9 @@
 
     ap_hard_timeout("read script header", r);
 
+    /* temporary place to hold headers to merge in later */
+    merge = ap_make_table(r->pool, 10);
+
     while (1) {
 
 	if ((*getsfunc) (w, MAX_STRING_LEN - 1, getsfunc_data) == 0) {
@@ -547,10 +556,10 @@
 	    ap_table_add(r->err_headers_out, w, l);
 	}
 	else {
-	    /* XXX: there is an O(n^2) space attack possible here */
-	    ap_table_merge(r->err_headers_out, w, l);
+	    ap_table_add(merge, w, l);
 	}
     }
+    ap_overlap_tables(r->err_headers_out, merge, AP_OVERLAP_TABLES_MERGE);
 }
 
 static int getsfunc_FILE(char *buf, int len, void *f)
Index: modules/standard/mod_cern_meta.c
===================================================================
RCS file: /export/home/cvs/apache-1.3/src/modules/standard/mod_cern_meta.c,v
retrieving revision 1.34
diff -u -r1.34 mod_cern_meta.c
--- mod_cern_meta.c	1998/08/09 17:36:29	1.34
+++ mod_cern_meta.c	1998/08/10 06:54:08
@@ -226,13 +226,17 @@
     {NULL}
 };
 
-/* XXX: another O(n^2) attack here */
+/* XXX: this is very similar to ap_scan_script_header_err_core...
+ * are the differences deliberate, or just a result of bit rot?
+ */
 static int scan_meta_file(request_rec *r, FILE *f)
 {
     char w[MAX_STRING_LEN];
     char *l;
     int p;
+    table *tmp_headers;
 
+    tmp_headers = ap_make_table(r->pool, 5);
     while (fgets(w, MAX_STRING_LEN - 1, f) != NULL) {
 
 	/* Delete terminal (CR?)LF */
@@ -278,9 +282,10 @@
 	    r->status_line = ap_pstrdup(r->pool, l);
 	}
 	else {
-	    ap_table_set(r->headers_out, w, l);
+	    ap_table_set(tmp_headers, w, l);
 	}
     }
+    ap_overlap_tables(r->headers_out, tmp_headers, AP_OVERLAP_TABLES_SET);
     return OK;
 }
 





Mime
View raw message