Re: local_ip vs local_domain

> I know that local_domain is more efficient than local_ip. Unfortunately,
> as an ISP, we have so many domains that it is impractical to list them all
> in the squid.conf. We have far less nets, so I am wondering if the
> added expense of doing lots of DNS lookups would be worth not going
> through our parent cache. Any hints on this?

I had been meaning to write some code like this below for another
project anyway, so I've made it a bit more general and pedagogic
than I need for myself in the hope that this might be useful
in squid to perform efficient lookups of both local IP CIDR blocks
(nets) and simple addresses.

#include <stdio.h>
#include <stdlib.h>

static int debug = (0!=0);

typedef struct btree {
  struct btree *bit[2];
  char *domain;
} btree;

void bprinttree(btree *root, int depth, char *results)
{
  if (root == NULL) {
    printf("Empty\n");
    return;
  }
  if ((root->bit[0] == NULL) && (root->bit[1] == NULL)) {
    printf("%s -> %s\n", results, root->domain);
    return;
  } else if (root->domain != NULL) {
    printf("%s -> %s\n", results, root->domain);
  }
  results[depth] = '0'; results[depth+1] = '\0';
  if (root->bit[0] != NULL) bprinttree(root->bit[0], depth+1, results);
  results[depth] = '1'; results[depth+1] = '\0';
  if (root->bit[1] != NULL) bprinttree(root->bit[1], depth+1, results);
}

void printtree(btree *root)
{
  char results[33];
  printf("\nNetmask tree:\n");
  bprinttree(root, 0, results);
}

btree *newnode(void)
{
  btree *tmp =(struct btree *) malloc(sizeof(btree));
  tmp->bit[0] = NULL;
  tmp->bit[1] = NULL;
  tmp->domain = NULL;
  return(tmp);
}

void addbrule(btree **rootp, long bits, int bitsleft, char *domain)
{
#define root (*rootp)
  long firstbit = bits & (1L<<31L);
  if (root == NULL) root = newnode();
  if (bitsleft <= 0) {
    root->domain = domain;
    /*printf(" -> %s\n", domain);*/
    return;
  }
  if (firstbit == 0L) {
    if (debug) printf("0");
    addbrule(&root->bit[0], bits << 1L, bitsleft-1L, domain);
  } else {
    if (debug) printf("1");
    addbrule(&root->bit[1], bits << 1L, bitsleft-1L, domain);
  }
#undef root
}

void addrule(btree **rootp, int a, int b, int c, int d, long bits, char *domain)
{
  printf("%0d.%0d.%0d.%0d/%0ld -> %s\n", a, b, c, d, bits, domain);
  if (debug) printf("Bit-tree: \"");
  addbrule(rootp, (((((a<<8)|b)<<8)|c)<<8)|d, bits, domain);
  if (debug) printf("\"\n");
}

void btest(btree *root, long bits, int bitsleft, char **bestguessp)
{
#define bestguess (*bestguessp)
  if (root->domain != NULL) bestguess = root->domain;
  if (bitsleft == 0) {
    if (root->domain != NULL) {
      if (debug) printf(": %s\n", root->domain);
    } else {
      if (debug) printf("UKNOWN\n");
    }
    return;
  }
  bitsleft -= 1;
  if ((root->bit[0] == NULL) && (root->bit[1] == NULL)) {
    if (debug) printf(": %s\n", bestguess);
    return;
  }
  if ((bits & (1L << 31L)) == 0L) {
    if (root->bit[0] == NULL) {
      if (root->domain != NULL) {
        if (debug) printf("%s\n", root->domain);
      } else {
        if (debug) printf("0 <-- 0 is bad here\n");
      }
      return;
    }
    if (debug) printf("0");
    btest(root->bit[0], bits<<1L, bitsleft, &bestguess);
  } else {
    if (root->bit[1] == NULL) {
      if (root->domain != NULL) {
        if (debug) printf("%s\n", root->domain);
      } else {
        if (debug) printf("1 <-- 1 is bad here\n");
      }
      return;
    }
    if (debug) printf("1");
    btest(root->bit[1], bits<<1L, bitsleft, &bestguess);
  }
#undef bestguess
}

void test(btree *root, int a, int b, int c, int d)
{
char *bestguess = "No patterns defined";
  btest(root, (((((a<<8)|b)<<8)|c)<<8)|d, 32, &bestguess);
  printf("%0d.%0d.%0d.%0d ... %s\n", a,b,c,d, bestguess);
}

int main(int argc, char **argv)
{
btree *root = NULL;

  printf("Add rules:\n");
  addrule(&root, 0,0,0,0, 0, "global");
  addrule(&root, 204,117,188,0, 24, "backbone");
  addrule(&root, 204,117,189,0, 24, "local dialup");
  addrule(&root, 127,0,0,0, 8, "localhost");
  addrule(&root, 167,114,209,20, 32, "localhost");
  addrule(&root, 167,114,208,0, 19, "regional");
  printtree(root);
  printf("\nTest rules:\n");
  test(root, 204,117,177,1);
  test(root, 204,117,188,1);
  test(root, 127,0,0,1);
  test(root, 167,114,209,20);
  test(root, 167,114,209,3);
  test(root, 255,255,255,255);
  test(root, 167,114,1,1);
  test(root, 128,113,107,1);
  exit(0);
  return(0);
}

PS The project I need this code for is to take the output
from tcpdump and count the volume of bytes traversing the
net from different sources - in particular, web traffic
so I can get stats on who is bypassing the cache and
how much it is costing us in bandwidth. I tried the
cachemgr today for the first time and couldn't find
a display of the style:

pages fetched directly: 500Mb
data found in our cache: 200Mb
data found in sibling cache xxx.com: 100Mb
data found in national cache it.cache.nlanr.net: 50Mb

ie something that would let me easily see how much
bandwidth I had saved...

G
Received on Thu Apr 17 1997 - 00:42:10 MDT