Return-Path: Mailing-List: contact apreq-dev-help@httpd.apache.org; run by ezmlm Delivered-To: mailing list apreq-dev@httpd.apache.org Received: (qmail 12691 invoked from network); 15 Dec 2000 01:48:05 -0000 Received: from mail4.mia.bellsouth.net (205.152.144.16) by locus.apache.org with SMTP; 15 Dec 2000 01:48:05 -0000 Received: from mumonkan.sunstarsys.com (adsl-61-20-87.mia.bellsouth.net [208.61.20.87]) by mail4.mia.bellsouth.net (3.3.5alt/0.75.2) with ESMTP id UAA14814 for ; Thu, 14 Dec 2000 20:54:10 -0500 (EST) Received: (from joe@localhost) by mumonkan.sunstarsys.com (8.11.0/8.11.0) id eBF1m5P19372; Thu, 14 Dec 2000 20:48:05 -0500 Sender: joe@sunstarsys.com To: apreq-dev@httpd.apache.org Subject: list.c,h reference From: Joe Schaefer Date: 14 Dec 2000 20:48:05 -0500 In-Reply-To: Joe Schaefer's message of "13 Dec 2000 23:21:02 -0500" Message-ID: Lines: 24 User-Agent: Gnus/5.0802 (Gnus v5.8.2) Emacs/20.5 MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" X-Spam-Rating: locus.apache.org 1.6.2 0/1000/N --=-=-= Here's the libapreq patch that uses list.c,h for dynamic memory allocation. I left the debugging flags on since it still needs testing (especially w.r.t. file upload integrity- I haven't checked this). I made quite a few changes to the multipart_buffer.c code to show off how using lists makes the coding considerably easier (at least to me :). In particular, I replaced next_line with read_line and changed the other internal functions to operate on the output string from the list instead. Since the list memory is reused for each pass, and freed once the POST data is parsed, it should be more efficient than previous attempts. --=-=-= Content-Type: text/x-patch Content-Disposition: attachment; filename=libapreq.patch Content-Description: list.c,h reference diff -Nur libapreq-0.31_01/MANIFEST libapreq-0.31_02/MANIFEST --- libapreq-0.31_01/MANIFEST Sat May 1 02:44:27 1999 +++ libapreq-0.31_02/MANIFEST Thu Dec 14 20:25:55 2000 @@ -23,6 +23,8 @@ c/apache_cookie.c c/multipart_buffer.h c/multipart_buffer.c +c/list.c +c/list.h eg/c/testapreq/mod_testapreq.c eg/c/testapreq/mod_testapreq.module eg/c/testapreq/Makefile.tmpl diff -Nur libapreq-0.31_01/c/Makefile.PL libapreq-0.31_02/c/Makefile.PL --- libapreq-0.31_01/c/Makefile.PL Sat May 1 02:44:28 1999 +++ libapreq-0.31_02/c/Makefile.PL Sat Dec 9 20:12:03 2000 @@ -12,8 +12,8 @@ use Cwd; my $pwd = fastcwd; - my @objs = qw(apache_request.o apache_cookie.o multipart_buffer.o); - $MY_LD_RUN_PATH = "$Config{installsitearch}/auto/libapreq:$pwd"; + my @objs = qw(apache_request.o apache_cookie.o multipart_buffer.o list.o); + $MY_LD_RUN_PATH = "$Config{installsitearch}/auto/libapreq:$pwd"; WriteMakefile( #grr, problems with things finding libapreq.so, sort out later. diff -Nur libapreq-0.31_01/c/apache_request.c libapreq-0.31_02/c/apache_request.c --- libapreq-0.31_01/c/apache_request.c Thu Nov 30 14:33:04 2000 +++ libapreq-0.31_02/c/apache_request.c Thu Dec 14 18:09:45 2000 @@ -379,6 +379,7 @@ int blen; if (!header) { + ap_list_destroy(mbuff->list); return OK; } @@ -420,6 +421,7 @@ } if (!(upload->fp = ApacheRequest_tmpfile(req))) { + ap_list_destroy(mbuff->list); return HTTP_INTERNAL_SERVER_ERROR; } @@ -444,8 +446,8 @@ if (r->args) { split_to_parms(req, r->args); - } - + } + ap_list_destroy(mbuff->list); return OK; } diff -Nur libapreq-0.31_01/c/list.c libapreq-0.31_02/c/list.c --- libapreq-0.31_01/c/list.c Wed Dec 31 19:00:00 1969 +++ libapreq-0.31_02/c/list.c Thu Dec 14 17:45:14 2000 @@ -0,0 +1,385 @@ +/* list.c - linked lists for apache + * + * Author: Joe Schaefer + * Date: Dec 10, 2000 + * + * for inclusion in asf projects + */ + +#include "list.h" + + +/****************************************************\ + * internal subroutines * +\****************************************************/ + + +list_node *ap_list_node_make(char *src, int length, int size, list_node *prev, + list_node *next) +{ + list_node *node = (list_node *) malloc( sizeof(list_node) ); + + if ( node == NULL ) + return NULL; + + node->data = (char *) malloc(size+1) ; /* leave room for null character */ + if ( node->data == NULL ) { + free(node); + return NULL; + } + + length = min(size,length); + + if (length > 0) + memcpy(node->data, src, length); + + node->length = length; + node->free = size - length; + node->prev = prev; + node->next = next; + + return node; +} + + +list_node *ap_sublist_destroy(list_node *node, char *data) +{ + + if (node == NULL) + return NULL; + + if (data != NULL) { + memcpy(data, node->data, node->length); + data += node->length; + } + + free(node->data); /* node->data != NULL */ + + ap_sublist_destroy(node->next, data); + + free(node); + return NULL; +} + + + +/****************************************************\ + * external routines * +\****************************************************/ + + +/*************************************************** + * ap_list_make(r, e, s, m) - initialize list + * + * r = request object (only needed for logging purposes) + * e = 1 or 2 preallocated elements, + * depending on user preference (1 is usually better) + * s = size of initial elements + * m = maxsize of temporary elements: + * new elements would be twice the size of previous + * ones- this caps their size at m + * + */ + +list_header *ap_list_make(request_rec *r, int elts, int size, int maxsize) +{ + list_node *node; + list_header *self = (list_header *) malloc(sizeof(list_header)); + + if (self == NULL) + return NULL; + + self->r = r; + self->maxsize = maxsize; + self->total = 0; + + node = ap_list_node_make(NULL, 0, size, NULL, NULL); + self->first = node; + self->current = node; + self->nelts = 1; + self->pelts = 1; + + if (node == NULL) { + free(self); + return NULL; + } + + while(--elts > 0) { + if (node == NULL) + break; + + node->next = ap_list_node_make(NULL, 0, size, node, NULL); + node = node->next; + self->nelts += 1; + self->pelts += 1; + + } + +#ifdef DEBUG + ap_log_rerror(LIST_ERROR, "ap_list_make: %d preallocated elts, %d bytes each", + self->pelts, size); +#endif + + return self; + +} + + +/*************************************************** + * ap_list_push(l,s,n) - add data to list + * + * l = list object + * s = source data + * n = size of data + * + * + * This routine handles dynamic memory allocation + * necessary for appending the data in s to the + * list. After filling up the preallocated list + * elements, it creates temporary elements that + * are twice as large as the previous element + * ( up to l->maxsize ). + * + * The temporary list elements are typically freed + * by ap_list_flush or ap_list_collapse. + * + */ + +list_node *ap_list_push(list_header *self, char *src, int size) +{ + + list_node *node = self->current; + char *insert = node->data + node->length; + int avail = node->free; + + if (size <= avail) { + memcpy(insert, src, size); + node->length += size; + node->free -= size; + self->total += size; + +#ifdef DEBUG + ap_log_rerror(LIST_ERROR, "ap_list_push: %d bytes added", size); +#endif + return node; + } + + memcpy(insert, src, avail); + node->length += avail; + node->free = 0; + src += avail; + size -= avail; + self->total += avail; + avail = node->length; /* set up for loop */ + +#ifdef DEBUG + ap_log_rerror(LIST_ERROR, "ap_list_push: %d bytes", avail); +#endif + + if (node->next != NULL) { + self->current = node->next; + return ap_list_push(self, src, size); + + } else { + + for ( ; size > 0 ; avail=node->free) { + /* doubling buffer size */ + avail = min(2*avail,self->maxsize); + + node = node->next = self->current = + ap_list_node_make(src, size, avail, self->current, NULL); + + self->nelts += 1; + self->total += min(avail,size); + src += avail; + size -= avail; + +#ifdef DEBUG + ap_log_rerror(LIST_ERROR, "ap_list_push: %d nodes, %d bytes", self->nelts, avail); +#endif + + } + } + + return node; +} + + +/*************************************************** + * ap_list_collapse(l) + * + * l = list + * + * this collapses the list onto the first + * element and returns a pointer to it. + * + * specifically: + * + * * temporary list elements are removed + * + * * preallocated list elements are cleared of data + * (allocated memory for data isn't freed, though) + * + * * all data is moved to a single (null-terminated) + * string in l->first (which is the return value) + * + * note that the string in l->first can be quite + * large, and should be considered volatile as + * the list is ready to reuse this memory for + * new data to insert in l->first. + * + */ + +char *ap_list_collapse(list_header *self) +{ + list_node *node = self->first; + int total = self->total; + char *data; + + + if (self->current == self->first) { + data = node->data; + node->free += node->length; + data[total]='\0'; /* needs total + 1 bytes avail */ + + } else { + + data = (char*) malloc(total + 1); + if (data == NULL) + return NULL; + + ap_list_flush(self, data); + free(node->data); + + node->data = data; + node->free = total; + + } + + node->length = 0; + self->total = 0; + return data; +} + + +/*************************************************** + * ap_list_flush(l,d) + * + * l = list + * d = output data string + * + * if d==NULL, this sub removes all + * temporary elements and clears + * preallocated ones to prepare the + * list for reuse. + * + * if d!=NULL, the data currently + * contained in the list is copied + * to d while flushing the list. As + * such, d must be larger than l->total + * (the data will be null-terminated). + * + */ + +list_header *ap_list_flush(list_header *self, char *data) +{ + int n; + list_node *node = self->current = self->first; + + for (n = 0 ; n < self->pelts ; node = node->next, ++n) { + if (node == NULL) + break; + if (node->length == 0) + continue; + if (data != NULL) { + memcpy(data, node->data, node->length); + data += node->length; + } + node->free += node->length; + self->total -= node->length; + +#ifdef DEBUG + ap_log_rerror(LIST_ERROR, "ap_list_flush: pelt %d = %d bytes", n, node->length); +#endif + node->length = 0; + + } + + if (n=0) + return NULL; + + if (node != NULL) + node->prev->next = NULL; + + ap_sublist_destroy(node, data); + data[self->total] = 0; + +#ifdef DEBUG + ap_log_rerror(LIST_ERROR, "ap_list_flush: %d nodes destroyed, %d bytes of data", + self->nelts - self->pelts, strlen(data)); +#endif + + self->nelts = self->pelts = n; + self->total = 0; + + return self; +} + + +/*************************************************** + * ap_list_destroy(l) + * + * l = list + * + * frees all memory allocated to the list. + * + */ + + +int ap_list_destroy(list_header *self) +{ + ap_sublist_destroy(self->first, NULL); + free(self); + + return 0; +} + + +/*************************************************** + * ap_list_generate(l,f,v,b,s) + * + * l = list + * f = function used to generate data (read prototype) + * v = object to read from (filehandle, buffer, etc.) + * b = buffer for new data + * s = size of buffer + * + * generates the list by repeatedly calling f(v,b,s) + * and using its return value for the amount of new data + * in b. stops after a 0 read, collapses the list, and + * returns a pointer to the full data read into the + * list (now in list->first). + * + * as consecutive calls to ap_list_generate will overwrite + * previously returned data, the return value should be + * copied immediately. + * + */ + +char *ap_list_generate(list_header *self, + int (*get)(void*, void*, size_t), + void *v, + void *buf, + size_t bufsize) +{ + int bytes; + + while( bytes = (*get)(v,buf,bufsize) ) { + ap_list_push(self, (char *) buf, bytes); + } + + return ap_list_collapse(self); + +} + + diff -Nur libapreq-0.31_01/c/list.h libapreq-0.31_02/c/list.h --- libapreq-0.31_01/c/list.h Wed Dec 31 19:00:00 1969 +++ libapreq-0.31_02/c/list.h Mon Dec 11 08:23:33 2000 @@ -0,0 +1,52 @@ +/* list.h - linked lists for apache + * + * Author: Joe Schaefer + * Date: Dec 10, 2000 + * + * for asf projects + */ + +#include "httpd.h" +#include "http_config.h" +#include "http_core.h" +#include "http_log.h" +#include "http_main.h" +#include "http_protocol.h" +#include "util_script.h" + +#define max(A,B) ((A) > (B)) ? (A) : (B) +#define min(A,B) ((A) < (B)) ? (A) : (B) +#define LIST_ERROR APLOG_MARK, APLOG_NOERRNO|APLOG_ERR, self->r +#define DEBUG 1 + + +/* structures */ + +typedef struct node { /* private */ + int length, free; /* length + free = size */ + char* data; + struct node *next, *prev; +} list_node; + +typedef struct { /* public */ + request_rec *r; + list_node *first, *current; /* begginning and write-to node in list */ + int maxsize; /* largest size of data string */ + int nelts; /* num of nodes */ + int total; /* total data (characters) in list */ + int pelts; /* number of preallocated nodes */ +} list_header; + +/* methods */ + +list_header *ap_list_make(request_rec *r, int elts, int size, int maxsize); +list_node *ap_list_push(list_header *self, char *src, int size); +char *ap_list_collapse(list_header *self); +list_header *ap_list_flush(list_header *self, char *data); +int ap_list_destroy(list_header *self); +char *ap_list_generate(list_header *list, + int (*get)(void*, void*, size_t), + void *v, + void *buf, + size_t bufsize); + diff -Nur libapreq-0.31_01/c/multipart_buffer.c libapreq-0.31_02/c/multipart_buffer.c --- libapreq-0.31_01/c/multipart_buffer.c Sun Dec 3 17:59:31 2000 +++ libapreq-0.31_02/c/multipart_buffer.c Thu Dec 14 20:30:34 2000 @@ -89,10 +89,12 @@ return ptr; } + /* - fill up the buffer with client data. + fill up the buffer with client data, literally. returns number of bytes added to buffer. */ + int fill_buffer(multipart_buffer *self) { int bytes_to_read, actual_read = 0; @@ -104,100 +106,127 @@ /* calculate the free space in the buffer */ bytes_to_read = self->bufsize - self->bytes_in_buffer; + /* read the required number of bytes */ - if(bytes_to_read > 0) + while (bytes_to_read > 0) { + int got; char *buf = self->buffer + self->bytes_in_buffer; + ap_hard_timeout("[libapreq] multipart_buffer.c:fill_buffer", self->r); - actual_read = ap_get_client_block(self->r, buf, bytes_to_read); + got = ap_get_client_block(self->r, buf, bytes_to_read); ap_kill_timeout(self->r); - /* update the buffer length */ - if(actual_read > 0) - self->bytes_in_buffer += actual_read; + if (got == 0) break; + + bytes_to_read -= got; + actual_read += got; + self->bytes_in_buffer += got; } return actual_read; } /* - gets the next CRLF terminated line from the input buffer. - if it doesn't find a CRLF, and the buffer isn't completely full, returns - NULL; otherwise, returns the beginning of the null-terminated line, - minus the CRLF. - + reads CRLF terminated lines from the input buffer, incorporating + RFC822 MIME-folding into output. Will read one paragraph (up to + a CRLFCRLF sequence), strips CR(\r)'s and breaks lines by LF(\n). note that we really just look for LF terminated lines. this works around a bug in internet explorer for the macintosh which sends mime boundaries that are only LF terminated when you use an image submit button in a multipart/form-data form. */ -char* next_line(multipart_buffer *self) + +/* reads up to CRLFCRLF (end of header); analagous to mbr */ +int read_line(multipart_buffer *self, char* buf, int bytes) { + int len, max; + char *bound; + + /* fill buffer if needed */ + if(bytes > self->bytes_in_buffer) fill_buffer(self); + if (self->bytes_in_buffer == 0) return 0; + + /* look for a newline, read data up to and including that point + also leave room for possible MIME-folding */ + if( bound = memchr(self->buf_begin, '\n', self->bytes_in_buffer - 1) ) + max = (bound - self->buf_begin) + 1; + else + max = self->bytes_in_buffer - 1; + + /* maximum number of bytes we are reading */ + len = max < bytes-1 ? max : bytes-1; + + /* copy the data */ + memcpy(buf, self->buf_begin, len); + + self->bytes_in_buffer -= len; + self->buf_begin += len; + + if ( bound ) { + + /* drop CR if CRLF */ + if((len > 1) && (buf[len-2] == '\r')) + buf[--len-1] = '\n'; + + /* drop '\n' if MIME-folding */ + if(bound[1]== '\t' || bound[1]==' ') len--; + + } + + /* stop reading when first character is '\n' */ + if (buf[0]=='\n') len = 0; + +#ifdef DEBUG + ap_log_rerror(MPB_ERROR, "read_line: %d bytes", len); +#endif + + return len; + +} + + +/* returns the next LF terminated line, + points src at next line */ +char* get_line(char **src) { - /* look for LF in the data */ - char* line = self->buf_begin; - char* ptr = memchr(self->buf_begin, '\n', self->bytes_in_buffer); + char *line, *ptr; + int len; + + if (*src == NULL) return NULL; + + line = *src; + ptr = strchr(line, '\n'); + len = strlen(line); /* LF found */ if(ptr) { - /* terminate the string, remove CRLF */ - if((ptr - line) > 0 && *(ptr-1) == '\r') *(ptr-1) = 0; - else *ptr = 0; + *ptr = 0; /* bump the pointer */ - self->buf_begin = ptr + 1; - self->bytes_in_buffer -= (self->buf_begin - line); + if (ptr-line>=len-1) + *src = NULL; /* done */ + else + *src = ptr + 1; /* next */ + } /* no LF found */ else - { - /* buffer isn't completely full, fail */ - if(self->bytes_in_buffer < self->bufsize) - return NULL; - - /* return entire buffer as a partial line */ - line[self->bufsize] = 0; - self->buf_begin = ptr; - self->bytes_in_buffer = 0; - } - - return line; -} + *src = NULL; -/* returns the next CRLF terminated line from the client */ -char* get_line(multipart_buffer *self) -{ - char* ptr = next_line(self); - - if(!ptr) - { - fill_buffer(self); - ptr = next_line(self); - } - -#ifdef DEBUG - ap_log_rerror(MPB_ERROR, "get_line: '%s'", ptr); -#endif - - return ptr; + return line; } /* finds a boundary */ -int find_boundary(multipart_buffer *self, char *boundary) +int find_boundary(char **src, char *boundary) { - int len, bound_len = strlen(boundary); - char *line; - + char *line; + /* loop thru lines */ - while( (line = get_line(self)) ) + while( line = get_line(src) ) { -#ifdef DEBUG - ap_log_rerror(MPB_ERROR, "find_boundary: '%s' ?= '%s'", - line, boundary); -#endif - /* finished if we found the boundary */ if(strcmp(line, boundary) == 0) return 1; @@ -218,6 +247,7 @@ int minsize = strlen(boundary)+6; if(minsize < FILLUNIT) minsize = FILLUNIT; + self->list = ap_list_make(r, 1, minsize, 32 * minsize); self->r = r; self->buffer = (char *) ap_pcalloc(r->pool, minsize+1); self->bufsize = minsize; @@ -234,14 +264,19 @@ table *multipart_buffer_headers(multipart_buffer *self) { table *tab; - char *line; + char *line, *hdr, buf[FILLUNIT]; + + tab = ap_make_table(self->r->pool, 10); + + hdr = ap_list_generate(self->list, + (int(*)(void*,void*,size_t)) read_line, + (void *)self, (void *)buf, (size_t)sizeof(buf)); /* didn't find boundary, abort */ - if(!find_boundary(self, self->boundary)) return NULL; + if(!find_boundary(&hdr, self->boundary)) return NULL; - /* get lines of text, or CRLF_CRLF */ - tab = ap_make_table(self->r->pool, 10); - while( (line = get_line(self)) && strlen(line) > 0 ) + /* get lines of text */ + while( line = get_line(&hdr) ) { /* add header to table */ char *key = line; @@ -294,16 +329,30 @@ len = max < bytes-1 ? max : bytes-1; /* if we read any data... */ - if(len > 0) + if (len > 0) { /* copy the data */ memcpy(buf, self->buf_begin, len); buf[len] = 0; - if(bound && len > 0 && buf[len-1] == '\r') buf[len-1] = 0; /* update the buffer */ + if(bound && buf[len-1] == '\r') buf[--len] = 0; + self->bytes_in_buffer -= len; self->buf_begin += len; + + } + + + if(len==0 && bound) + { + + /* done reading- move buffer to front of self->boundary */ + while (*(self->buf_begin) != '-') + { + (self->buf_begin)++; + (self->bytes_in_buffer)--; + } } #ifdef DEBUG @@ -313,22 +362,21 @@ return len; } -/* - XXX: this is horrible memory-usage-wise, but we only expect - to do this on small pieces of form data. -*/ + char *multipart_buffer_read_body(multipart_buffer *self) { - char buf[FILLUNIT], *out = ""; + char buf[FILLUNIT], *out = NULL; - while(multipart_buffer_read(self, buf, sizeof(buf))) - out = ap_pstrcat(self->r->pool, out, buf, NULL); + out = ap_list_generate(self->list, + (int(*)(void*,void*,size_t)) multipart_buffer_read, + (void *)self, (void *)buf, (size_t)sizeof(buf)); #ifdef DEBUG - ap_log_rerror(MPB_ERROR, "multipart_buffer_read_body: '%s'", out); + ap_log_rerror(MPB_ERROR, "multipart_buffer_read_body: '%d' bytes", strlen(out)); #endif return out; + } /* eof if we are out of bytes, or if we hit the final boundary */ diff -Nur libapreq-0.31_01/c/multipart_buffer.h libapreq-0.31_02/c/multipart_buffer.h --- libapreq-0.31_01/c/multipart_buffer.h Mon Nov 27 15:19:24 2000 +++ libapreq-0.31_02/c/multipart_buffer.h Sat Dec 9 21:04:04 2000 @@ -1,6 +1,7 @@ #include "apache_request.h" +#include "list.h" -/*#define DEBUG 1*/ +#define DEBUG 1 #define FILLUNIT (1024 * 5) #define MPB_ERROR APLOG_MARK, APLOG_NOERRNO|APLOG_ERR, self->r @@ -8,12 +9,13 @@ /* request info */ request_rec *r; long request_length; - + /* read buffer */ char *buffer; char *buf_begin; int bufsize; int bytes_in_buffer; + list_header *list; /* boundary info */ char *boundary; --=-=-= HTH. -- Joe Schaefer --=-=-=--