1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
|
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.apache.catalina.webresources;
import java.util.BitSet;
import java.util.Enumeration;
import java.util.jar.JarEntry;
import java.util.jar.JarFile;
/**
* This class represents the contents of a jar by determining whether a given resource <b>might</b> be in the cache,
* based on a bloom filter. This is not a general-purpose bloom filter because it contains logic to strip out characters
* from the beginning of the key. The hash methods are simple but good enough for this purpose.
*/
public final class JarContents {
private final BitSet bits1;
private final BitSet bits2;
/**
* Constant used by a typical hashing method.
*/
private static final int HASH_PRIME_1 = 31;
/**
* Constant used by a typical hashing method.
*/
private static final int HASH_PRIME_2 = 17;
/**
* Size of the fixed-length bit table. Larger reduces false positives, smaller saves memory.
*/
private static final int TABLE_SIZE = 2048;
/**
* Parses the passed-in jar and populates the bit array.
*
* @param jar the JAR file
*/
public JarContents(JarFile jar) {
Enumeration<JarEntry> entries = jar.entries();
bits1 = new BitSet(TABLE_SIZE);
bits2 = new BitSet(TABLE_SIZE);
while (entries.hasMoreElements()) {
JarEntry entry = entries.nextElement();
String name = entry.getName();
int startPos = 0;
// If the path starts with a slash, that's not useful information.
// Skipping it increases the significance of our key by
// removing an insignificant character.
boolean precedingSlash = name.charAt(0) == '/';
if (precedingSlash) {
startPos = 1;
}
// Versioned entries should be added to the table according to their real name
if (name.startsWith("META-INF/versions/", startPos)) {
int i = name.indexOf('/', 18 + startPos);
if (i > 0) {
int version = Integer.parseInt(name.substring(18 + startPos, i));
if (version <= Runtime.version().feature()) {
startPos = i + 1;
}
}
if (startPos == name.length()) {
continue;
}
}
// Find the correct table slot
int pathHash1 = hashcode(name, startPos, HASH_PRIME_1);
int pathHash2 = hashcode(name, startPos, HASH_PRIME_2);
bits1.set(pathHash1 % TABLE_SIZE);
bits2.set(pathHash2 % TABLE_SIZE);
// While directory entry names always end in "/", application code
// may look them up without the trailing "/". Add this second form.
if (entry.isDirectory()) {
pathHash1 = hashcode(name, startPos, name.length() - 1, HASH_PRIME_1);
pathHash2 = hashcode(name, startPos, name.length() - 1, HASH_PRIME_2);
bits1.set(pathHash1 % TABLE_SIZE);
bits2.set(pathHash2 % TABLE_SIZE);
}
}
}
/**
* Simple hashcode of a portion of the string. Typically we would use substring, but memory and runtime speed are
* critical.
*
* @param content Wrapping String.
* @param startPos First character in the range.
*
* @return hashcode of the range.
*/
private int hashcode(String content, int startPos, int hashPrime) {
return hashcode(content, startPos, content.length(), hashPrime);
}
private int hashcode(String content, int startPos, int endPos, int hashPrime) {
int h = hashPrime / 2;
for (int i = startPos; i < endPos; i++) {
h = hashPrime * h + content.charAt(i);
}
if (h < 0) {
h = h * -1;
}
return h;
}
/**
* Method that identifies whether a given path <b>MIGHT</b> be in this jar. Uses the Bloom filter mechanism.
*
* @param path Requested path. Sometimes starts with "/WEB-INF/classes".
* @param webappRoot The value of the webapp location, which can be stripped from the path. Typically it is
* "/WEB-INF/classes".
*
* @return Whether the prefix of the path is known to be in this jar.
*/
public boolean mightContainResource(String path, String webappRoot) {
int startPos = 0;
if (path.startsWith(webappRoot)) {
startPos = webappRoot.length();
}
if (path.charAt(startPos) == '/') {
// ignore leading slash
startPos++;
}
// calculate the hash lazily and return a boolean value for this path
return (bits1.get(hashcode(path, startPos, HASH_PRIME_1) % TABLE_SIZE) &&
bits2.get(hashcode(path, startPos, HASH_PRIME_2) % TABLE_SIZE));
}
}
|
