Patch for reading long src or dst ACL's + lookup speedup

In article <199609172002.WAA01869@adv.IAEhv.nl> I wrote:

>Would the following idea work: when the lookup of an address/host in an
>ACL is successful, move that node to the first position of the list
>(shouldn't be to difficult with pointers). The list will automatically get
>sorted by LRU-order (last recently used) and because most accesses from/to
>a site come in bursts this should give some serious improvements. Just an
>idea, couldn't find the time to try it myself :-(.

I've made a patch to read src and dst ACL's from a file (one entry per
line), the new commands are 'acl <name> src_file <file>' and 'acl <name>
dst_file <file>'.

Furthermore I added a small patch to implement the ACL lookup speedup
described above: a matched record in an ACL will be moved to the second
position of the list (the first position is somewhat more difficult). This
speedup does not work for negated ACL's (!<acl-name>) as the whole list
still needs to be searched. But for my purpose (a long list of IP addresses
authorized to use the proxy) it should be an improvement.

The patch was made for Squid 1.1.beta3.

Arjan

--- acl.h.orig Wed Sep 25 21:37:20 1996
+++ acl.h Wed Sep 25 21:01:07 1996
@@ -32,7 +32,9 @@
 typedef enum {
     ACL_NONE,
     ACL_SRC_IP,
+ ACL_SRC_FILE_IP,
     ACL_DST_IP,
+ ACL_DST_FILE_IP,
     ACL_SRC_DOMAIN,
     ACL_DST_DOMAIN,
     ACL_TIME,
--- acl.c.orig Wed Sep 18 23:39:27 1996
+++ acl.c Wed Sep 25 22:15:02 1996
@@ -56,6 +56,7 @@
 static int aclMatchTime __P((struct _acl_time_data * data, time_t when));
 static intlist *aclParseIntlist __P((void));
 static struct _acl_ip_data *aclParseIpList __P((void));
+static struct _acl_ip_data *aclParseIpFile __P((char *));
 static intlist *aclParseMethodList __P((void));
 static intlist *aclParseProtoList __P((void));
 static struct _relist *aclParseRegexList __P((void));
@@ -70,8 +71,12 @@
 {
     if (!strcmp(s, "src"))
         return ACL_SRC_IP;
+ if (!strcmp(s, "src_file"))
+ return ACL_SRC_FILE_IP;
     if (!strcmp(s, "dst"))
         return ACL_DST_IP;
+ if (!strcmp(s, "dst_file"))
+ return ACL_DST_FILE_IP;
     if (!strcmp(s, "domain"))
         return ACL_DST_DOMAIN;
     if (!strcmp(s, "dstdomain"))
@@ -278,6 +283,79 @@
     return head;
 }
 
+static struct _acl_ip_data *
+aclParseIpFile(char *file)
+{
+ char t[256], *p = NULL;
+ struct _acl_ip_data *head = NULL;
+ struct _acl_ip_data **Tail = &head;
+ struct _acl_ip_data *q = NULL;
+ LOCAL_ARRAY(char, addr1, 256);
+ LOCAL_ARRAY(char, addr2, 256);
+ LOCAL_ARRAY(char, mask, 256);
+ FILE *f;
+
+ if ((f = fopen(file, "r")) == NULL) {
+ debug(28, 0, "aclParseIpFile: file %s not found\n", file);
+ return(NULL);
+ }
+
+ while (fgets(t, 256, f) != NULL) {
+ q = xcalloc(1, sizeof(struct _acl_ip_data));
+ if (!strcasecmp(t, "all")) {
+ q->addr1.s_addr = 0;
+ q->addr2.s_addr = 0;
+ q->mask.s_addr = 0;
+ } else {
+ p = t;
+ memset(addr1, 0, sizeof(addr1));
+ memset(addr2, 0, sizeof(addr2));
+ memset(mask, 0, sizeof(mask));
+
+ /* Split the adress in addr1-addr2/mask */
+ strncpy(addr1, p, strcspn(t, "-/"));
+ p += strcspn(t, "-/");
+ if (*p == '-') {
+ p++;
+ strncpy(addr2, p, strcspn(t, "/"));
+ p += strcspn(p, "/");
+ }
+ if (*p == '/') {
+ p++;
+ strcpy(mask, p);
+ }
+ /* Decode addr1 */
+ if (!decode_addr(addr1, &q->addr1, &q->mask)) {
+ debug(28, 0, "%s line %d: %s\n",
+ cfg_filename, config_lineno, config_input_line);
+ debug(28, 0, "aclParseIpFile: Ignoring invalid IP acl entry: unknown first address '%s'\n", addr1);
+ safe_free(q);
+ continue;
+ }
+ /* Decode addr2 */
+ if (*addr2 && !decode_addr(addr2, &q->addr2, &q->mask)) {
+ debug(28, 0, "%s line %d: %s\n",
+ cfg_filename, config_lineno, config_input_line);
+ debug(28, 0, "aclParseIpFile: Ignoring invalid IP acl entry: unknown second address '%s'\n", addr1);
+ safe_free(q);
+ continue;
+ }
+ /* Decode mask */
+ if (*mask && !decode_addr(mask, &q->mask, NULL)) {
+ debug(28, 0, "%s line %d: %s\n",
+ cfg_filename, config_lineno, config_input_line);
+ debug(28, 0, "aclParseIpFile: Ignoring invalid IP acl entry: unknown netmask '%s'\n", mask);
+ safe_free(q);
+ continue;
+ }
+ }
+ *(Tail) = q;
+ Tail = &q->next;
+ }
+ fclose(f);
+ return head;
+}
+
 static struct _acl_time_data *
 aclParseTimeSpec(void)
 {
@@ -447,6 +525,14 @@
     case ACL_DST_IP:
         A->data = (void *) aclParseIpList();
         break;
+ case ACL_SRC_FILE_IP:
+ case ACL_DST_FILE_IP:
+ if ((t = strtok(NULL, w_space)) == NULL) {
+ debug(28, 0, "aclParseAclLine: no filename found\n");
+ return;
+ }
+ A->data = (void *) aclParseIpFile(t);
+ break;
     case ACL_SRC_DOMAIN:
     case ACL_DST_DOMAIN:
         A->data = (void *) aclParseDomainList();
@@ -630,7 +716,10 @@
 {
     struct in_addr h;
     unsigned long lh, la1, la2;
+ struct _acl_ip_data *first, *prev;
 
+ first = data; /* remember first element, this will never be moved */
+ prev = NULL; /* previous element in the list */
     while (data) {
         h.s_addr = c.s_addr & data->mask.s_addr;
         debug(28, 3, "aclMatchIp: h = %s\n", inet_ntoa(h));
@@ -639,6 +728,13 @@
         if (!data->addr2.s_addr) {
             if (h.s_addr == data->addr1.s_addr) {
                 debug(28, 3, "aclMatchIp: returning 1\n");
+ if (prev != NULL) {
+ /* shift the element just found to the second position
+ in the list */
+ prev->next = data->next;
+ data->next = first->next;
+ first->next = data;
+ }
                 return 1;
             }
         } else {
@@ -651,6 +747,7 @@
                 return 1;
             }
         }
+ prev = data;
         data = data->next;
     }
     debug(28, 3, "aclMatchIp: returning 0\n");
@@ -729,9 +826,11 @@
     debug(28, 3, "aclMatchAcl: checking '%s'\n", acl->cfgline);
     switch (acl->type) {
     case ACL_SRC_IP:
+ case ACL_SRC_FILE_IP:
         return aclMatchIp(acl->data, checklist->src_addr);
         /* NOTREACHED */
     case ACL_DST_IP:
+ case ACL_DST_FILE_IP:
         hp = ipcache_gethostbyname(r->host, IP_LOOKUP_IF_MISS);
         if (hp) {
             for (k = 0; *(hp->h_addr_list + k); k++) {
Received on Wed Sep 25 1996 - 13:45:41 MDT