1 # layer.tcl --
2 #
3 # A layered web cache object.
4 #
5 # Copyright (c) 1998-2002 The Regents of the University of California.
6 # All rights reserved.
7 #
8 # Redistribution and use in source and binary forms, with or without
9 # modification, are permitted provided that the following conditions are met:
10 #
11 # A. Redistributions of source code must retain the above copyright notice,
12 # this list of conditions and the following disclaimer.
13 # B. Redistributions in binary form must reproduce the above copyright notice,
14 # this list of conditions and the following disclaimer in the documentation
15 # and/or other materials provided with the distribution.
16 # C. Neither the names of the copyright holders nor the names of its
17 # contributors may be used to endorse or promote products derived from this
18 # software without specific prior written permission.
19 #
20 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS IS''
21 # AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 # IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 # ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR
24 # ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 # DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
26 # SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
27 # CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
28 # OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29 # OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30
31
32 #
33 # A layered web cache object. It does cooperative multi-resolution media
34 # caching. In the current implementation, the only layer-able object is
35 # jpeg image, since we have extended the progressive jpeg library. But
36 # the code should be organized enough so it is easy to extend this to
37 # video and audio (or other data types) in the future.
38 #
39
40 Class WebCacheApplication/Layer -superclass WebCacheApplication -configuration {
41 layersDir /tmp/
42 }
43
44 #
45 # The constructor.
46 #
47 WebCacheApplication/Layer public init { argv } {
48 $self next $argv
49
50 # directory to store temporary layers or blocks
51 $self instvar layers_dir_
52 $self create_dir [$self get_option layersDir]
53 #set layers_dir_ [glob [$self get_option layersDir]]
54 set layers_dir_ [glob [$self get_option cacheDir]]
55
56 # progressive jpeg
57 # we only use 5 recoding levels: 10 (full), 8, 6, 3, 1
58 # this table given an existing level tells you what level
59 # the image should be reduced to.
60 $self instvar pjpeg_recoding_table_
61 set pjpeg_recoding_table(10) 8
62 set pjpeg_recoding_table(9) 8
63 set pjpeg_recoding_table(8) 6
64 set pjpeg_recoding_table(7) 6
65 set pjpeg_recoding_table(6) 3
66 set pjpeg_recoding_table(5) 3
67 set pjpeg_recoding_table(4) 3
68 set pjpeg_recoding_table(3) 1
69 set pjpeg_recoding_table(2) 1
70 }
71
72 WebCacheApplication/Layer private init_argv { argv } {
73 set o [$self options]
74
75 $o register_option -cacheDir cacheDir
76 $o register_option -cacheSize cacheSize
77 $o register_option -layersDir layersDir
78
79 return [$o parse_args $argv]
80 }
81
82
83 #
84 # Called by srm if another cache needs to recover the specified data.
85 # The difference here is we give back a layer of layer-able object
86 # instead of the whole object.
87 #
88 WebCacheApplication/Layer public read_data { source cid seqno } {
89 $self instvar index_ layers_dir_
90
91 set url [$self cid_2_name $source $cid]
92 if { $url == "" || ![info exists index_($url)] } {
93 return ""
94 }
95
96 # check whether url is a layer-able object
97 # pass to parent method if not
98 set data_type [$self is_layerable $url]
99 if { "$data_type" == "" } {
100 $self next $source $cid $seqno
101 return
102 }
103
104 # progressive jpeg
105 if { "$data_type" == "jpeg" } {
106 set num_layers [jpeg_is_progressive $index_($url)]
107
108 if { $num_layers > $seqno } {
109 set layer [expr $seqno + 1]
110 set fn [file join $layers_dir_ tmp[clock clicks]]
111
112 jpeg_getrange_progressive $index_($url) $fn $layer $layer
113
114 return $fn
115 } else {
116 return ""
117 }
118 }
119 }
120
121
122 #
123 # Called by the cache control after winning the response timer war. The
124 # difference here is if the url is a layer-able object, we send out the
125 # object layer by layer. This means we allocate a new adu to each layer,
126 # but within the same container.
127 #
128 WebCacheApplication/Layer public send_data { url } {
129 $self instvar sockets_ source_ index_ cid_names_ proxy_ layers_dir_
130
131 puts "layer: send_data $url"
132
133 # check whether url is a layer-able object
134 # pass to parent method if not
135 set data_type [$self is_layerable $url]
136 if { "$data_type" == "" } {
137 $self next $url
138 return
139 }
140
141 # check if stored on disk at all
142 if [info exists index_($url)] {
143 # allocate a cid for this url if one does not exist
144 set p [split [$self name_2_cid $url] ,]
145 set source [lindex $p 0]
146 set cid [lindex $p 1]
147 if { $cid == "" || $source != $source_} {
148 set cid [srm_calloc $source_ 0 $url]
149 set cid_names_($source_,$cid) $url
150 }
151
152 # send the data to the session, while allocating
153 # increasing adu sequecne number to each layer.
154 # for now, the only data type is progressive jpeg
155 if { "$data_type" == "jpeg" } {
156 puts " filename: $index_($url)"
157
158 set num_layers [jpeg_is_progressive $index_($url)]
159
160 # change from baseline jpeg to progressive jpeg
161 # this means we have 10 layers of enhancements
162 if { $num_layers == 0 } {
163 set fn [file join $layers_dir_ tmp[clock clicks]]
164 jpeg_tran_progressive $index_($url) $fn
165 file rename -force $fn $index_($url)
166
167 set num_layers 10
168 }
169
170 for { set i 0 } { $i < $num_layers } { incr i } {
171 # create a temp file for this layer
172 set fn [file join $layers_dir_ tmp[clock clicks]]
173
174 # get the layer
175 jpeg_getrange_progressive $index_($url) $fn $i $i
176
177 # read it from the file
178 set f [open $fn]
179 fconfigure $f -translation binary
180 set blk ""
181 while { ![eof $f] } {
182 append blk [read $f 4096]
183 }
184 close $f
185
186 # remove this temp file
187 file delete $fn
188
189 # send the layer using srm
190 srm_send $source_ $cid $i $blk
191 }
192 }
193
194 # callback to proxy to hand data to browser
195 if [info exists sockets_($url)] {
196 $proxy_ done_fetch $url $sockets_($url) $index_($url)
197 unset sockets_($url)
198
199 pust 9
200 }
201 } else {
202 # need to fetch data from origin server
203 $self fetch $url
204 }
205 }
206
207
208 #
209 # Called when received data from the cache session. The difference here
210 # is the cache can choose not to store the whole object if it is
211 # layer-able. Also, the data is not broken up into aduss or layers if it
212 # is layer-able. Assume that a layer-able object is already broken into
213 # layers and transported layer-by-layer with each adu in a container
214 # representing a layer.
215 #
216 WebCacheApplication/Layer public recv_data { source cid seqno fn } {
217 $self instvar proxy_ control_ sockets_ index_ passed_layers_ buffered_layers_ buffered_fns_ layers_dir_
218
219 set url [$self cid_2_name $source $cid]
220
221 puts "layer: recv_data $url $seqno"
222
223 # check whether url is layer-able
224 # pass to parent method if not
225 set data_type [$self is_layerable $url]
226 if { "$data_type" == "" } {
227 $self next $source $cid $seqno
228 return
229 }
230
231 # progressive jpeg
232 if { "$data_type" == "jpeg" } {
233 # pass to client if the request originiated from here
234 # also, check whether to store the layer in cache, if so
235 # put it there.
236
237 # an enhancement layer
238 if [info exists passed_layers_($url)] {
239 set expected_seqno [expr $passed_layers_($url) + 1]
240 } else {
241 set expected_seqno 0
242 }
243
244 if { $seqno == $expected_seqno } {
245 if [info exists sockets_($url)] {
246 $proxy_ done_partial_fetch $url $sockets_($url) $fn
247 }
248 if [$self should_store jpeg $url $seqno $fn] {
249 $self put $url $fn $seqno
250 }
251 set passed_layers_($url) $seqno
252
253 set n [expr $seqno + 1]
254 while { $n <= 9 } {
255 if { [info exists buffered_layers_($url)] && \
256 [set idx [lsearch $buffered_layers_($url) $n]] != -1 } {
257
258 if [$self should_store jpeg $url $n $fn] {
259 $self put $url $buffered_fns_($url,$n) $n
260 }
261
262 set passed_layers_($url) $n
263 set buffered_layers_($url) \
264 [lreplace $buffered_layers_($url) $idx $idx]
265 unset buffered_fns_($url,$n)
266
267 incr n
268
269 if { $n == 9 } {
270 # last layer can close and forget socket
271 if [info exists sockets_($url)] {
272 $proxy_ done_fetch $url $sockets_($url) $fn
273 unset sockets_($url)
274 }
275 if [info exists passed_layers_($url)] {
276 unset passed_layers_($url)
277 }
278 if [info exists buffered_layers_($url)] {
279 unset buffered_layers_($url)
280 }
281
282 # tell cache control to cancel timers related for this url
283 $control_ cancel_all_timers $url
284 } else {
285 # still more layers to come, so don't close down socket yet
286 if [info exists sockets_($url)] {
287 $proxy_ done_partial_fetch $url $sockets_($url) \
288 $buffered_fns_($url,$n)
289 }
290 }
291 } else {
292 break
293 }
294 }
295 } elseif { $seqno > $expected_seqno } {
296 # first check whether this is original data or repair
297 # look whether some part of image is already stored on disk
298
299 # <FILL IN>
300
301 puts "layer: buffering data $url $seqno"
302
303 # remember whic layer are buffered
304 if ![info exists buffered_layers_($url)] {
305 set buffered_layers_($url) ""
306 }
307 set buffered_layers_($url) [lappend $buffered_layers_($url) $seqno]
308
309 # move the layer into another temp file
310 set buffered_fns_($url,$seqno) [file join $layers_dir_ buf[clock clicks]]
311 file rename $fn $buffered_fns_($url,$seqno)
312 }
313 }
314 }
315
316 #
317 # Algorithm to decide whether to store this layer. Should only be called
318 # from recv_data. This assumes the url is a layer-able object. The heuristics
319 # we use are: if the request originated from here, always store everything.
320 #
321 WebCacheApplication/Layer private should_store { data_type url seqno fn } {
322 $self instvar sockets_ used_ total_
323
324 # check whether request originated from us
325 if [info exists sockets_($url)] {
326 return 1
327 }
328
329 if { "$data_type" == "jpeg" } {
330 # only store the first 3 layers of the image
331 if { $seqno > 2 } {
332 return 0
333 } else {
334 return 1
335 }
336 }
337 }
338
339
340 #
341 # Uses the function should_store to decide whether to recover. That is,
342 # if the cache will not store the object, then there is no point to
343 # recover the losses anyway.
344 #
345 WebCacheApplication/Layer public should_recover { source cid sseq eseq } {
346
347 set url [$self cid_2_name $source $cid]
348 set data_type [$self is_layerable $url]
349
350 if { $data_type == "" } {
351 $self next $source $cid $sseq $eseq
352 } else {
353 # use the start seqno as hints
354 # FIXME foo
355 return [$self should_store $data_type $url $sseq foo]
356 }
357 }
358
359
360 #
361 # Make room in cache by evicting or reducing (or both) objects selected
362 # by the LRU algorithm. <i>needed</i> denotes the amount of space needed
363 # in B.
364 #
365 WebCacheApplication/Layer public make_room { needed } {
366 $self instvar index_ lru_ layers_dir_ used_ pjpeg_recoding_table_
367
368 set cleared 0
369
370 while { $cleared < needed } {
371
372 # find the lru object in cache
373 set url [lindex $lru_ 0]
374 set fn $index_($url)
375 set fs [file size $fn]
376
377 set data_type [$self is_layerable $fn]
378 if { $data_type == "" } {
379 set cleared [expr $cleared + $fs]
380
381 $self flush_url $url
382 } elseif { "$data_type" == "jpeg" } {
383 set num_layers [jpeg_is_progressive $fn]
384
385 if { $num_layers == 1 } {
386 $self flush_url $url
387
388 set cleared [expr $cleared + $fs]
389 } else {
390 set reduced_layers $pjpeg_recoding_table_($num_layers)
391
392 set dstfn [file join $layers_dir_ tmp[clock clicks]]
393 jpeg_reduce_progressive $fn $dstfn $reduced_layers
394 file rename $dstfn $fn
395
396 set cleared [expr $cleared + [expr $fs - [file size $fs]]]
397 }
398 }
399 }
400 }
401
402
403 #
404 # Called to initiate the loop to access the cache. The difference is the
405 # cache needs to determine whether the url is a layer-able object. If
406 # only the base layers of the object is available, the cache do a repair
407 # request to get the additional layers.
408 #
409 WebCacheApplication/Layer public get { url { socket "" } } {
410 $self instvar index_ sockets_ proxy_ wcc_ passed_layers_ buffered_layers_
411
412 puts "layer: get $url"
413
414 # check if stored on disk at all or url is a layer-able object
415 # pass to parent method if not
416 set data_type [$self is_layerable $url]
417
418 if { "$data_type" == "" || ![info exists index_($url)] } {
419 $self next $url $socket
420 return
421 }
422
423 # do the lru business
424 $self push_lru $url
425
426 if { $socket != "" } {
427 set sockets_($url) $socket
428 }
429
430 # progressive jpeg
431 if { "$data_type" == "jpeg" } {
432 # check whether whole or partial object is stored
433 set num_layers [jpeg_is_progressive $index_($url)]
434
435 if { $num_layers == 0 || $num_layers == 10 } {
436 # pass to client if whole
437 $proxy_ done_fetch $url $sockets_($url) $index_($url)
438 unset sockets_($url)
439 } else {
440 # pass the existing layers to clients first, and
441 # remember what has been passed to keep order
442 $proxy_ done_partial_fetch $url $sockets_($url) \
443 $index_($url)
444 set passed_layers_($url) [expr $num_layers - 1]
445 set buffered_layers_($url) ""
446
447 # do downcall for a repair request to get rest
448 # of the layers from other caches
449 set m [$self name_2_cid $url]
450 set source [lindex $m 0]
451 set cid [lindex $m 1]
452
453 srm_recover $source $cid $num_layers 9
454 }
455 }
456 # no other data types yet
457
458 }
459
460
461 #
462 # Put contents of url into the cache. If url is a layer-able object,
463 # we need to enhance the existing layers instead of overwriting them.
464 # Assume for a layer-able object, it is already layered, and the layers
465 # are given to this method in-order.
466 #
467 WebCacheApplication/Layer public put { url fn { seqno 0 } } {
468 $self instvar index_ layers_dir_ used_ total_ wcc_
469
470 puts "layer: put $url"
471
472 # check whether url is a layer-able object
473 # pass to parent method if not
474 set data_type [$self is_layerable $url]
475 if { "$data_type" == "" } {
476 $self next $url $fn
477 return
478 }
479
480 # first check whether there is enough space in cache
481 # if not need to make room
482 set fs [file size $fn]
483 if { [expr $fs + $used_] > $total_ } {
484 # need to make room in cache
485 $self make_room [expr $fs - ($total_ - $used_)]
486 }
487
488 # progressive jpeg
489 if { "$data_type" == "jpeg" } {
490 # if this is the first layer or a baseline jpeg file,
491 # need to create file etc, so pass to parent method
492 if { $seqno == 0 } {
493 $self next $url $fn
494 return
495 }
496
497 # include this enhancement layer into the jpeg image
498 set dstfn [file join $layers_dir_ tmp[clock clicks]]
499 jpeg_enhance_progressive $index_($url) $dstfn $fn 1
500 file rename -force $dstfn $index_($url)
501 }
502 }
503
504
505 WebCacheApplication/Layer private is_layerable { url } {
506
507 # for now, we can only do layers on jpeg images
508 set ext [string trimleft [file extension $url] .]
509 if [regexp -nocase {jpeg|jpg} $ext] {
510 return jpeg
511 } else {
512 return ""
513 }
514 }
515
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.