001 package edu.harvard.deas.hyperenc.vsat;
002
003 import java.io.Serializable;
004 import java.util.ArrayList;
005 import java.util.Collections;
006 import java.util.Date;
007 import java.util.HashMap;
008 import java.util.LinkedList;
009 import java.util.List;
010 import java.util.Map;
011 import java.util.Queue;
012 import java.util.Random;
013
014 import edu.harvard.deas.hyperenc.util.Pair;
015
016 /**
017 * A PageDatabase that implements lookup as described in Section II-B1 of M.
018 * Rabin's 2005 paper ("Provably Unbreakable Hyper-Encryption In the Limited
019 * Access Model")
020 * <p>
021 * When first generated, pages are not associated with a key. When looking up a
022 * page, KeyedPageDatabase checks for any pages already associated with the
023 * given key. If there is one, and the page is not stale, it returns and then
024 * destroys it. Otherwise, it assigns the key to the next available page.
025 * <p>
026 * If the database becomes too large (as a result of an abundance of request
027 * keys only being used once), the database discards random key-page pairs to
028 * free up space.
029 * <p>
030 * A KeyedPageDatabase periodically checks if its pages are stale. A page is
031 * considered stale if it has been requested once, and some amount of time (the
032 * <i>stale page time</i>) has passed before a second request is made. If a page
033 * is found to be stale, it is discarded (destroyed). For performance reasons,
034 * stale pages might not be detected/destroyed immediately, but it is guaranteed
035 * that a stale page will never be returned to a client.
036 */
037 public class KeyedPageDatabase
038 extends Thread
039 implements Serializable, PageDatabase
040 {
041 private static final long serialVersionUID = 1L;
042
043 /** Controls debugging output. */
044 private static final boolean DEBUG = false;
045
046 /**
047 * The <i>stale page time</i> is the number of milliseconds after which a
048 * page that has been requested once is considered stale and discarded.
049 * STALE_PAGE_TIME is the stale page time for this PageDatabase; its
050 * default value is DEFAULT_STALE_PAGE_TIME.
051 */
052 public static final long DEFAULT_STALE_PAGE_TIME = 1000 * 60 * 60 * 24 * 3; // three days
053 private long STALE_PAGE_TIME;
054
055 /** Maximum number of PageCreators to run simultaneously. */
056 private static final int MAX_CONCURRENCY = 5;
057
058 /**
059 * Maximum allowable number of pages that have been requested exactly once.
060 * (These pages are stored in a map, with associated request keys.)
061 */
062 private static final int MAP_MAX_SIZE = 1000;
063
064 /**
065 * Maximum number of "fresh" (never-served) pages to keep. (These pages are
066 * stored in a stack, with pages being removed from the top as needed.)
067 */
068 private static final int STACK_MAX_SIZE = 100;
069
070 /**
071 * Minimum number of "fresh" pages to have on hand. When the page stack falls
072 * below this size, new pages are generated.
073 */
074 private static final int STACK_MIN_SIZE = 50;
075
076 /**
077 * The collection of pages that have been requested exactly once. Each key is
078 * a request key, and the associated value is the page served in response to
079 * that key. All manipulation of this map must be done while synchronized on
080 * pageDB.
081 */
082 private Map<Integer,Pair<VSatPage,Date>> pageDB;
083
084 /**
085 * The collection of pages that have never been requested. All manipulation of
086 * this queue must be done while synchronized on pageDB.
087 */
088 private Queue<VSatPage> backs;
089
090 /**
091 * The most recent time when we checked pageDB for stale pages.
092 */
093 private Date lastStaleCheckTime;
094
095 /** The number of PageCreators running at the moment. */
096 private Integer running;
097 private Integer runningMutex;
098
099 /**
100 * Random number generator for use when evicting a random page from the
101 * database.
102 */
103 private Random fumbles;
104
105 /**
106 * Creates a new KeyedPageDatabase. Generates MAX_NUM_PAGES and inserts them
107 * into the database.
108 * @param stalePageTime
109 * The stale page time for this database.
110 * @see #DEFAULT_STALE_PAGE_TIME
111 */
112 public KeyedPageDatabase(long stalePageTime)
113 {
114 this.STALE_PAGE_TIME = stalePageTime;
115
116 pageDB = Collections.synchronizedMap(new HashMap<Integer,Pair<VSatPage,Date>>());
117 backs = new LinkedList<VSatPage>();
118 running = new Integer(0);
119 runningMutex = new Integer(0);
120
121 lastStaleCheckTime = new Date();
122
123 // this doesn't have to be secure
124 fumbles = new Random();
125
126 // generate our initial complement of pages
127 generateNewPages();
128
129 checkRep();
130 }
131
132 public KeyedPageDatabase() {
133 this(DEFAULT_STALE_PAGE_TIME);
134 }
135
136 /**
137 * Enforce class invariants.
138 */
139 private void checkRep() {
140 if (STALE_PAGE_TIME <= 0) {
141 throw new RuntimeException("The STALE_PAGE_TIME is non-positive.");
142 }
143 }
144
145 /**
146 * @return The stale page time, in seconds.
147 */
148 public long getStalePageTime() {
149 checkRep();
150 return STALE_PAGE_TIME;
151 }
152
153 /**
154 * Evicts a random page from the database. May only be called while
155 * synchronized on pageDB.
156 */
157 private void fumble() {
158 Object[] keys = pageDB.keySet().toArray();
159 int i = fumbles.nextInt(keys.length);
160 pageDB.remove(keys[i]);
161 if (DEBUG) System.out.println("Database too large; fumbling page "+i+"!");
162 checkRep();
163 }
164
165 /**
166 * Goes through pageDB and throws out all the stale pages. MUST NOT be called
167 * while synchronized on pageDB.
168 */
169 private void sweepStalePages() {
170 if (DEBUG) System.out.println("Sweeping stale pages");
171
172 synchronized (pageDB) {
173 // First, find all the stale pages for later removal (we can't remove
174 // them now because we're iterating over them!)
175 List<Integer> staleKeys = new ArrayList<Integer>();
176 for (int key : pageDB.keySet()) {
177 Pair<VSatPage,Date> p = pageDB.get(key);
178 Date now = new Date();
179 if (p.second().getTime() + STALE_PAGE_TIME < now.getTime()) {
180 staleKeys.add(key);
181 }
182 }
183
184 // Now, remove them
185 for (int staleKey : staleKeys) {
186 if (DEBUG) System.out.println("Removing stale page " + staleKey);
187 Pair<VSatPage,Date> p = pageDB.remove(staleKey);
188 assert(p != null);
189 }
190 }
191
192 lastStaleCheckTime = new Date();
193 }
194
195 /**
196 * Returns the maximum number of pages that can be stored in the database.
197 * This counts only pages in the map (that is, the maximum number of
198 * requested-once pages that this database will keep track of).
199 *
200 * @return maximum number of pages that can be stored in the map
201 */
202 @Override
203 public int getMaxPages() {
204 return MAP_MAX_SIZE;
205 }
206
207 /**
208 * Returns the number of pages currently stored in this database that have
209 * been requested exactly once. That is, returns the number of pages in the
210 * map.
211 *
212 * @return number of pages in the map
213 */
214 @Override
215 public int getNumPages() {
216 return pageDB.size();
217 }
218
219 /**
220 * Returns the number of pages currently stored in this database that have
221 * never been requested. That is, returns the number of pages in the queue.
222 */
223 public int getQueueSize() {
224 return backs.size();
225 }
226
227 /** Get a page from the database.
228 @param key The key we are trying to match.
229 @return The page whose key matched the given key, or if none exists that is not stale,
230 then a new page that has never been served. Returns <code>null</code>
231 if the database is empty.
232 */
233 public byte[] getPage(int key)
234 {
235 checkRep();
236
237 // XXX is returning null really the right course of action? Maybe an
238 // exception would be more appropriate
239 VSatPage thisPage = null;
240
241 boolean makeNew=false;
242
243 //get closest page
244 synchronized (pageDB) {
245 // if there's already a page with the given key, check if it's stale
246 // if so, discard it; if not, return it
247 if (pageDB.containsKey(key)) {
248 Pair<VSatPage,Date> thisPair = pageDB.remove(key);
249 Date now = new Date();
250 if (thisPair.second().getTime() + STALE_PAGE_TIME > now.getTime()) {
251 thisPage = thisPair.first();
252 if (DEBUG) System.out.println("Serving page "+key+" from the hash.");
253 } else {
254 if (DEBUG) System.out.println("Page "+key+" from the hash is stale; discarding. (1st req: " + thisPair.second().getTime() + ", now: " + now.getTime() + ", stale after " + STALE_PAGE_TIME + "ms)");
255 }
256 }
257
258 if (thisPage == null) {
259 if (!backs.isEmpty()) {
260 thisPage = backs.remove();
261 pageDB.put(key, new Pair<VSatPage,Date>(thisPage, new Date()));
262 if (DEBUG) System.out.println("Serving page "+key+" from the stack.");
263
264 // database size management
265 if (backs.size() < STACK_MIN_SIZE)
266 makeNew = true;
267 if (pageDB.size() > MAP_MAX_SIZE)
268 fumble();
269 } else {
270 makeNew = true;
271 if (DEBUG) System.out.println("Underflow on page "+key+"!");
272 }
273 }
274 }
275
276 // If we haven't checked for stale pages recently, create a thread
277 // that will do it once this method returns
278 Date now = new Date();
279 if (lastStaleCheckTime.getTime() + STALE_PAGE_TIME < now.getTime())
280 sweepStalePages();
281
282 if (makeNew) generateNewPages();
283
284 checkRep();
285
286 return thisPage.getData();
287 }
288
289 /** Generate a new page and put it into the database */
290 private void generateNewPages()
291 {
292 // Spawn a thread to collect the page
293 PageCreator pc = new PageCreator();
294
295 synchronized (runningMutex) {
296 if (running.intValue() < MAX_CONCURRENCY) {
297 running = new Integer(1 + running.intValue());
298 pc.start();
299 }
300 }
301 }
302
303 private class PageCreator extends Thread {
304 public void run() {
305 boolean keepgoing=true;
306
307 //call a new TrueRandomSource to get file data
308 TrueRandomSource myRS;
309 if (DevRandomSource.randomDevice() != null) {
310 myRS = new DevRandomSource();
311 if (DEBUG)
312 System.out.println("Node: getting randomness from "+
313 DevRandomSource.randomDevice());
314 } else {
315 if (DEBUG)
316 System.out.println("Node: getting randomness from FileRandomSource");
317 myRS = new FileRandomSource();
318 }
319
320 VSatPage newPage = null;
321 byte[] data;
322
323
324 while (keepgoing) {
325 data=null;
326 do {
327 data = myRS.genRandomness();
328 } while (data == null);
329
330 //create a new VSatPage with this data
331 newPage = new VSatPage(data);
332
333 synchronized (pageDB) {
334 backs.add(newPage);
335 if (DEBUG) System.out.println("Added a page");
336 if (backs.size() >= STACK_MAX_SIZE)
337 keepgoing=false;
338 }
339 }
340
341 synchronized (runningMutex) {
342 running = new Integer(running.intValue() - 1);
343 }
344 }
345 }
346 }
347