WebCache/Digest.pm untested

filter: Statementstmt 0.0% 0 / 167 Branchbran 0.0% 0 / 18 Conditioncond 0.0% 0 / 3 MC/DCmcdc 0.0% 0 / 2 Subroutinesub 0.0% 0 / 32 Podpod 0.0% 0 / 26 totaltotal 0.0% 0 / 248 CC 10 SCAR 16.6
CC
10
Cov
0%
fetch
20.0
lookup
12.0
save
6.0
CRAP 5.3
1 # Copyright (c) 1998 Martin Hamilton. All rights reserved.
2  
3 # This program is free software; you can redistribute it and/or modify it
4 # under the same terms as Perl itself.
5  
6 # $Id: Digest.pm,v 1.2 1999/03/12 19:05:30 martin Exp $
7  
8 package WebCache::Digest;
9  
10 use strict;
11 use vars qw($VERSION);
12  
13 use Carp;
14 use IO::Socket;
15 use MD5;
16 use Sys::Hostname;
17  
18  
19 $VERSION = "1.00";
20  
21  
22 sub new {
23 my ($this, %args) = @_;
24 my $class = ref($this) || $this;
25 my ($a, $v);
26 my ($self) = {};
27  
28 while(($a, $v) = each %args) { $self->{$a} = $v; }
29 bless $self, $class;
30  
31 return $self;
32 }
33  
34  
35 sub create {
36 my($self,%args) = @_;
37 my($a, $v);
38  
39 # set defaults
40 $self->{capacity} = 500; # number of URLs in digest - variable
41 $self->{bits_per_entry} = 5; # bits per entry - set in store_digest.c
42  
43 # override defaults with arguments to object creation
44 while(($a, $v) = each %args) { $self->{$a} = $v; }
45  
46 $self->{size_in_bytes} =
47 int(($self->{capacity} * $self->{bits_per_entry} + 7) / 8);
48 $self->{bit_count} = $self->{size_in_bytes} * 8;
49  
50 # This is the actual digest, and it's initially all zeroes
51 @{ $self->{cdigest} } = unpack("C*", 0x00 x $self->{size_in_bytes});
52  
53 $self->{current_version} = 5;
54 $self->{required_version} = 3;
55 $self->{count} = 0;
56 $self->{del_count} = 0;
57 $self->{hash_func_count} = 4;
58 $self->{reserved_short} = 0;
59 $self->{reserved} = 0;
60 }
61  
62  
63 sub fetch {
64 my($self, %args) = @_;
65 my($sock, $digest, $digest_length, $content_length, $nread, $buffer);
66 my($host) = $args{host};
67 my($port) = $args{port};
68  
69 $sock = IO::Socket::INET->new(PeerAddr => $host, PeerPort => $port);
70 unless(defined($sock)) {
71 carp "$0: couldn't connect to the server $host on port $port: $!";
72 return 0;
73 }
74  
75 print $sock
76 "GET http://$host:$port/squid-internal-periodic/store_digest HTTP/1.0\r\n\r\n";
77  
78 # Skip HTTP headers - XXX need to check status code here
79 while(<$sock>) {
80 # print ">> skipping $_";
81 if (/^Content-Length: (\d+)/i) {
82 $content_length = $1;
83 $digest_length = $content_length - 128;
84 # print ">>>> got Content-Length of $content_length\n";
85 }
86 last if /^\r?$/;
87 }
88  
89 # Cache digest control block: (header for cache digest)
90 $nread = read($sock, $buffer, 128);# || die "$0: sysread failed: $!";
91 $self->{header} = $buffer;
92 # print "number of digest header bytes read: $nread\n";
93 # print "raw buffer:\n" . unpack("H*", $buffer) . "\n";
94  
95 $nread = read($sock, $buffer, $digest_length);
96  
97 # print "number of digest bytes read: $nread\n";
98 # print "raw buffer:\n" . unpack("H*", $buffer) . "\n";
99  
100 close($sock);
101 $self->unpack_header;
102 @{ $self->{cdigest} } = unpack("C*", $buffer);
103 return 1;
104 }
105  
106  
107 sub unpack_header {
108 my($self) = @_;
109  
110 ($self->{current_version}, $self->{required_version}, $self->{capacity},
111 $self->{count}, $self->{del_count}, $self->{size_in_bytes},
112 $self->{bits_per_entry}, $self->{hash_func_count},
113 $self->{reserved_short}, $self->{reserved})
114 = unpack("n n N N N N C C n C*", $self->{header});
115 }
116  
117  
118 sub pack_header {
119 my($self) = @_;
120  
121 $self->{header} = pack("n n N N N N C C n C104",
122 $self->current_version,
123 $self->required_version, $self->capacity,
124 $self->count, $self->del_count,
125 $self->size_in_bytes, $self->bits_per_entry,
126 $self->hash_func_count, $self->reserved_short,
127 $self->reserved);
128 }
129  
130  
131 sub dump_header {
132 my($self) = @_;
133  
134 return
135 "Current version: " . $self->current_version . "\n" .
136 "Required version: " . $self->required_version . "\n" .
137 "Capacity: " . $self->capacity . "\n" .
138 "Count: " . $self->count . "\n" .
139 "Deletion count: " . $self->del_count . "\n" .
140 "Size in bytes: " . $self->size_in_bytes . "\n" .
141 "Bits per entry: " . $self->bits_per_entry . "\n" .
142 "Hash function count: " . $self->hash_func_count . "\n";
143 }
144  
145  
146 # return raw header, digest, header fields...
147 sub header { shift->{header}; }
148 sub digest { pack("C*", @{ shift->{cdigest} }); }
149 sub current_version { shift->{current_version}; }
150 sub required_version { shift->{required_version}; }
151 sub capacity { shift->{capacity}; }
152 sub count { shift->{count}; }
153 sub del_count { shift->{del_count}; }
154 sub size_in_bytes { shift->{size_in_bytes}; }
155 sub bits_per_entry { shift->{bits_per_entry}; }
156 sub hash_func_count { shift->{hash_func_count}; }
157 sub reserved_short { shift->{reserved_short}; }
158 sub reserved { shift->{reserved}; }
159  
160  
161 # XXX - should load/save be network order or host order ?
162  
163 sub save {
164 my($self, $filename) = @_;
165  
166 unless(open(OUT, ">$filename")) {
167 carp "$0: couldn't open $filename: $!";
168 return 0;
169 }
170  
171 print OUT $self->pack_header;
172 print OUT $self->digest;
173 print "digest is... " . unpack("H*", $self->digest) . "\n";
174  
175 # XXX check written correct number of bytes here
176 close(OUT);
177 return 1;
178 }
179  
180  
181 sub load {
182 my($self, $filename) = @_;
183 my($size) = -s "$filename";
184 my($digest);
185  
186 unless(open(IN, "$filename")) {
187 carp "$0: couldn't open $filename: $!";
188 return 0;
189 }
190  
191 read(IN, $self->{header}, 128);
192 read(IN, $digest, $size - 128); # XXX check on size here
193  
194 close(IN);
195 $self->unpack_header;
196 @{ $self->{cdigest} } = unpack("C*", $digest);
197 return 1;
198 }
199  
200  
201 sub lookup {
202 my($self, $method, $url) = @_;
203 my(@hash_keys) = $self->calc_hash_key($method, $url);
204 my($hit_potential) = 0;
205 my($val, $i);
206  
207 for $i (0 .. 3) {
208 $val = $self->bit_test($hash_keys[$i]);
209 $val = 1 if $val >= 1;
210 $hit_potential += $val;
211 }
212  
213 return 1 if ($hit_potential >= 4);
214 return 0;
215 }
216  
217  
218 sub register {
219 my($self, $method, $url) = @_;
220 my(@hash_keys) = $self->calc_hash_key($method, $url);
221 my($i);
222  
223 for $i (0 .. 3) {
224 $self->bit_set($hash_keys[$i]);
225 }
226 $self->{count} ++;
227  
228 return 1;
229 }
230  
231  
232 sub bit_test {
233 my($self, $bit) = @_;
234 my($byte, $test);
235  
236 $byte = int($bit / 8);
237 $test = 1 << ($bit % 8);
238 return (@{ $self->{cdigest} }[$byte] & $test);
239 }
240  
241  
242 sub bit_set {
243 my($self, $bit) = @_;
244 my($byte, $test);
245  
246 $byte = int($bit / 8);
247 $test = 1 << ($bit % 8);
248 @{ $self->{cdigest} }[$byte] |= $test;
249  
250 ##printf("byte: %x, test: %x\n", $byte, $test);
251 #printf("bit: %x (%d), digest[$byte]: %x, test: %x (%x)\n",
252 # $bit, $bit, $digest[$byte], $test, $bit % 8);
253 }
254  
255  
256 sub calc_hash_key {
257 my($self, $method_p, $url_p) = @_;
258 my(%METHODS, $method, $url, $h, @temp_keys, @hash_keys);
259  
260 %METHODS = (
261 'get' => 0x1,
262 'post' => 0x2,
263 'put' => 0x3,
264 'head' => 0x4,
265 'connect' => 0x5,
266 'trace' => 0x6,
267 'purge' => 0x7,
268 );
269  
270 if ($METHODS{$method_p}) {
271 $method = pack("C", $METHODS{$method_p});
272 } else {
273 $method = pack("C", $METHODS{"get"});
274 }
275
276 $url = $method . $url_p;
277 #print "url (hex): " . unpack("H*", $url) . "\n";
278
279 $h = MD5->hash($url);
280 #print "\nh: " . unpack("H*", $h) . "\n";
281
282 @temp_keys = unpack("NNNN", MD5->hash($url));
283 #foreach ($i = 0; $i <= 3; $i++) {
284 # printf("temp_keys[$i] = %x\n", $temp_keys[$i]);
285 #}
286
287 $hash_keys[0] = $temp_keys[0] % ($self->{size_in_bytes} * 8);
288 $hash_keys[1] = $temp_keys[1] % ($self->{size_in_bytes} * 8);
289 $hash_keys[2] = $temp_keys[2] % ($self->{size_in_bytes} * 8);
290 $hash_keys[3] = $temp_keys[3] % ($self->{size_in_bytes} * 8);
291
292 #foreach ($i = 0; $i <= 3; $i++) {
293 # printf("hash_keys[$i] = %x (%d)\n", $hash_keys[$i], $hash_keys[$i]);
294 #}
295  
296 return @hash_keys;
297 }
298  
299  
300 sub test_digest {
301 my($self) = @_;
302 my($host) = $self->{host};
303 my($port) = $self->{port};
304 my(@retval) = ();
305 my($test_prefix, $path);
306  
307 $test_prefix = "http://$host:$port/squid-internal-static/icons";
308  
309 foreach $path (
310 "anthony-binhex.gif", "anthony-bomb.gif", "anthony-box.gif",
311 "anthony-box2.gif", "anthony-c.gif", "anthony-compressed.gif",
312 "anthony-dir.gif", "anthony-dirup.gif", "anthony-dvi.gif",
313 "anthony-f.gif", "anthony-image.gif", "anthony-image2.gif",
314 "anthony-layout.gif", "anthony-link.gif", "anthony-movie.gif",
315 "anthony-pdf.gif", "anthony-portal.gif", "anthony-ps.gif",
316 "anthony-quill.gif", "anthony-script.gif", "anthony-sound.gif",
317 "anthony-tar.gif", "anthony-tex.gif", "anthony-text.gif",
318 "anthony-unknown.gif", "anthony-xbm.gif", "anthony-xpm.gif"
319 ) {
320 push(@retval, "$test_prefix/$path");
321  
322 if ($self->lookup("GET", "$test_prefix/$path")) {
323 print "HIT ";
324 } else {
325 print "MISS ";
326 }
327 print "$test_prefix/$path\n";
328 }
329 }
330  
331  
332 1;
333  
334  
335 =head1 NAME
336  
337 WebCache::Digest - a Cache Digest implementation in Perl
338  
339 =head1 SYNOPSIS
340  
341 use WebCache::Digest;
342  
343 # fetching a digest via HTTP
344 $d = new WebCache::Digest;
345 $d->fetch("flibbertigibbet.swedish-chef.org", 3128);
346  
347 # dump header fields out for info
348 print STDERR $d->dump_header();
349  
350 # saving a digest
351 $d->save("flib");
352  
353 # loading a digest
354 $e = new WebCache::Digest;
355 $e->load("flib");
356  
357 # creating a new digests
358 $f = new WebCache::Digest;
359 $f->create; # defaults to a digest with 500 URL capacity
360  
361 # registering a URL and method in the digest
362 $f->register("get", "http://www.kha0s.org/">;
363 if ($f->lookup("get", "http://www.kha0s.org/">) {
364 print "hit!\n";
365 }
366  
367 # access to raw header and digest contents
368 print "header: " . unpack("H*", $f->header) . "\n";
369 print "digest: " . unpack("H*", $f->digest) . "\n";
370  
371 # access to digest header block elements
372 print "Current version: " . $f->current_version . "\n";
373 print "Required version: " . $f->required_version . "\n";
374 print "Capacity: " . $f->capacity . "\n";
375 print "Count: " . $f->count . "\n";
376 print "Deletion count: " . $f->del_count . "\n";
377 print "Size in bytes: " . $f->size_in_bytes . "\n";
378 print "Bits per entry: " . $f->bits_per_entry . "\n";
379  
380 =head1 DESCRIPTION
381  
382 This Perl module implements version 5 of the Cache Digest specification.
383 For more information about Cache Digests, check out the Squid FAQ:
384  
385 http://squid.nlanr.net/Squid/FAQ/FAQ-16.html
386  
387 A copy of the specification is included with this distribution as the
388 file F<cache-digest-v5.txt>.
389  
390 This code has been benchmarked on a 400MHz PII running Linux at 1866
391 lookups per second (or 112000 per minute, 560000 in five minutes),
392 with a cache digest of 500000 URLs.
393  
394 Cache Digests are summaries of the contents of WWW cache servers, which
395 are made available to other WWW caches and may also be used internally
396 within the server which generates them. They allow a WWW cache server
397 such as Squid to determine whether or not a particular Internet resource
398 (designated by its URL and the HTTP method which is being used to fetch
399 it) was cached at the time the digest was generated. Unlike other
400 mechanisms such as the Internet Cache Protocol (ICP - see RFC 2186),
401 Cache Digests do not generate a continuous stream of request/response
402 pairs, and do not add latency to each URL which is looked up.
403  
404 Since we provide routines to both lookup URLs in Cache Digests and also
405 register them in Cache Digests, it should be trivial to use this code
406 to devise innovative applications which take advantage of Cache Digests
407 to fool genuine WWW caches into treating them like WWW caches. For
408 example, mirror servers could register all the URLs which they're aware
409 of for the resources they mirror, so that cache servers which peer with
410 them will always get a cache 'hit' on the mirror server for any reference
411 to any of the mirrored resources.
412  
413 We also provide methods to store Cache Digests to disk and load them
414 back in again, in addition to creating new Digests and fetching them
415 from WWW caches which support the protocol. This can be used to take
416 a 'snapshot' of the state of a WWW cache at any particular point in
417 time, or for saving state if building a Cache Digest powered server.
418  
419 =head1 METHODS
420  
421 We only describe public methods and method arguments here. Anything
422 else should be considered private, at least for now.
423  
424 =over 4
425  
426 =item new
427  
428 Constructor function, creates a new WebCache::Digest object. As yet this
429 takes no arguments.
430  
431 =item create
432  
433 Fills in the data structures for a WebCache::Digest object, given the
434 number of lots to make available for URLs via the B<capacity> parameter.
435  
436 =item fetch
437  
438 Tries to fetch a Cache Digest from the machine whose domain name (or
439 IP address) and port number are specified (in this order) in the first
440 and second parameters. Returns 0 on failure, and 1 on success.
441  
442 =item dump_header
443  
444 Dump the fields in the Cache Digest header out as plain text to, e.g.
445 for debugging purposes.
446  
447 =item save
448  
449 Saves the WebCache::Digest object to the filename supplied as its parameter.
450 Returns 0 on failure, 1 on success.
451  
452 =item load
453  
454 Populates the WebCache::Digest object with contents of the filename supplied
455 as its parameter. Returns 0 on failure, 1 on success.
456  
457 =item lookup
458  
459 Given an HTTP method and URL (in that order) as parameters, try to look
460 them up in the Cache Digest. Returns 1 if the URL is a Cache Digest hit,
461 or 0 otherwise.
462  
463 =item register
464  
465 Given an HTTP method and URL (in that order) as parameters, register them
466 in the Cache Digest.
467  
468 =item header
469  
470 The raw Cache Digest header.
471  
472 =item digest
473  
474 The raw Cache Digest object, sans header.
475  
476 =item current_version
477  
478 The current version number from the Digest object.
479  
480 =item required_version
481  
482 The required version number from the Digest object. Implementations should
483 support at least this version for interoperability.
484  
485 =item capacity
486  
487 The number of 'slots' for URLs in the Digest.
488  
489 =item count
490  
491 The number of slots which have been filled.
492  
493 =item del_count
494  
495 The number of deletion attempts - Squid doesn't currently delete any
496 URLs (e.g. on their becoming stale) but simply discards them the next
497 time the Digest is rebuilt. Deleting one URL's information without
498 affecting others is impossible with Cache Digests as currently
499 conceived - where a given bit of the Digest may be used in looking up
500 multiple URLs.
501  
502 =item size_in_bytes
503  
504 The size of the Digest in bytes when stored in transfer format.
505  
506 =item bits_per_entry
507  
508 The number of bits in the Cache Digest consumed for each entry.
509  
510 =item hash_func_count
511  
512 The number of times the Cache Digest hash function (see the
513 specification for more information on this) is called for each URL.
514  
515 =back
516  
517 =head1 BUGS
518  
519 This is a first release, and there are probably lots of hideous bugs
520 waiting to catch you out - consider it pre-alpha code!
521  
522 Something else to watch out for is that the name may well change -
523 depending on feedback from the B<comp.lang.perl.modules> Usenet
524 conference.
525  
526 We use far too much memory - a more efficient approach to processing
527 the Cache Digest needs to be hacked in.
528  
529 We should be consistent and always use one form of arguments - either
530 hash array or fixed position arguments. Mixing the two is confusing.
531 However... most methods don't need named (hash array) arguments,
532 except for B<create>.
533  
534 =head1 COPYRIGHT
535  
536 Copyright (c) 1999, Martin Hamilton. All rights reserved.
537  
538 This program is free software; you can redistribute it and/or modify
539 it under the same terms as Perl itself.
540  
541 It was developed by the JANET Web Cache Service, which is funded by
542 the Joint Information Systems Committee (JISC) of the UK Higher
543 Education Funding Councils.
544  
545 =head1 AUTHOR
546  
547 Martin Hamilton E<lt>martinh@gnu.orgE<gt>
548