1 /*
2 * Copyright 2000-2002 Sun Microsystems, Inc. All Rights Reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
20 * CA 95054 USA or visit www.sun.com if you need additional information or
21 * have any questions.
22 *
23 */
24
25 package sun.jvm.hotspot.debugger;
26
27 /** This class implements an LRU page-level cache of configurable page
28 size and number of pages. It is configured with a PageFetcher
29 which enables it to transparently satisfy requests which span
30 multiple pages when one or more of those pages is not in the
31 cache. It is generic enough to be sharable among debugger
32 implementations. */
33
34 import sun.jvm.hotspot.utilities.*;
35
36 public class PageCache {
37 /** The pageSize must be a power of two and implicitly specifies the
38 alignment of pages. numPages specifies how many pages should be
39 cached. */
40 public PageCache(long pageSize,
41 long maxNumPages,
42 PageFetcher fetcher) {
43 checkPageInfo(pageSize, maxNumPages);
44 this.pageSize = pageSize;
45 this.maxNumPages = maxNumPages;
46 this.fetcher = fetcher;
47 addressToPageMap = new LongHashMap();
48 enabled = true;
49 }
50
51 /** This handles fetches which span multiple pages by virtue of the
52 presence of the PageFetcher. Throws UnmappedAddressException if
53 a page on which data was requested was unmapped. This can not
54 really handle numBytes > 32 bits. */
55 public synchronized byte[] getData(long startAddress, long numBytes)
56 throws UnmappedAddressException {
57 byte[] data = new byte[(int) numBytes];
58 long numRead = 0;
59
60 while (numBytes > 0) {
61 long pageBaseAddress = startAddress & pageMask;
62 // Look up this page
63 Page page = checkPage(getPage(pageBaseAddress), startAddress);
64 // Figure out how many bytes to read from this page
65 long pageOffset = startAddress - pageBaseAddress;
66 long numBytesFromPage = Math.min(pageSize - pageOffset, numBytes);
67 // Read them starting at the appropriate offset in the
68 // destination buffer
69 page.getDataAsBytes(startAddress, numBytesFromPage, data, numRead);
70 // Increment offsets
71 numRead += numBytesFromPage;
72 numBytes -= numBytesFromPage;
73 startAddress += numBytesFromPage;
74 }
75
76 return data;
77 }
78
79 public synchronized boolean getBoolean(long address) {
80 return (getByte(address) != 0);
81 }
82
83 public synchronized byte getByte(long address) {
84 return checkPage(getPage(address & pageMask), address).getByte(address);
85 }
86
87 public synchronized short getShort(long address, boolean bigEndian) {
88 return checkPage(getPage(address & pageMask), address).getShort(address, bigEndian);
89 }
90
91 public synchronized char getChar(long address, boolean bigEndian) {
92 return checkPage(getPage(address & pageMask), address).getChar(address, bigEndian);
93 }
94
95 public synchronized int getInt(long address, boolean bigEndian) {
96 return checkPage(getPage(address & pageMask), address).getInt(address, bigEndian);
97 }
98
99 public synchronized long getLong(long address, boolean bigEndian) {
100 return checkPage(getPage(address & pageMask), address).getLong(address, bigEndian);
101 }
102
103 public synchronized float getFloat(long address, boolean bigEndian) {
104 return checkPage(getPage(address & pageMask), address).getFloat(address, bigEndian);
105 }
106
107 public synchronized double getDouble(long address, boolean bigEndian) {
108 return checkPage(getPage(address & pageMask), address).getDouble(address, bigEndian);
109 }
110
111 /** A mechanism for clearing cached data covering the given region */
112 public synchronized void clear(long startAddress, long numBytes) {
113 long pageBaseAddress = startAddress & pageMask;
114 long endAddress = startAddress + numBytes;
115 while (pageBaseAddress < endAddress) {
116 flushPage(pageBaseAddress);
117 pageBaseAddress += pageSize;
118 }
119 }
120
121 /** A mechanism for clearing out the cache is necessary to handle
122 detaching and reattaching */
123 public synchronized void clear() {
124 // Should probably break next/prev links in list as well
125 addressToPageMap.clear();
126 lruList = null;
127 numPages = 0;
128 }
129
130 /** Disables the page cache; no further pages will be added to the
131 cache and all existing pages will be flushed. Call this when the
132 target process has been resumed. */
133 public synchronized void disable() {
134 enabled = false;
135 clear();
136 }
137
138 /** Enables the page cache; fetched pages will be added to the
139 cache. Call this when the target process has been suspended. */
140 public synchronized void enable() {
141 enabled = true;
142 }
143
144
145 //--------------------------------------------------------------------------------
146 // Internals only below this point
147 //
148
149 // This is implemented with two data structures: a hash table for
150 // fast lookup by a page's base address and a circular doubly-linked
151 // list for implementing LRU behavior.
152
153 private boolean enabled;
154 private long pageSize;
155 private long maxNumPages;
156 private long pageMask;
157 private long numPages;
158 private PageFetcher fetcher;
159 private LongHashMap addressToPageMap; // Map<long, Page>
160 private Page lruList; // Most recently fetched page, or null
161
162 /** Page fetcher plus LRU functionality */
163 private Page getPage(long pageBaseAddress) {
164 // Check head of LRU list first to avoid hash table lookup and
165 // extra list work if possible
166 if (lruList != null) {
167 if (lruList.getBaseAddress() == pageBaseAddress) {
168 // Hit. Return it.
169 return lruList;
170 }
171 }
172 // Long key = new Long(pageBaseAddress);
173 long key = pageBaseAddress;
174 Page page = (Page) addressToPageMap.get(key);
175 if (page == null) {
176 // System.err.println("** Cache miss at address 0x" + Long.toHexString(pageBaseAddress) + " **");
177 // Fetch new page
178 page = fetcher.fetchPage(pageBaseAddress, pageSize);
179 if (enabled) {
180 // Add to cache, evicting last element if necessary
181 addressToPageMap.put(key, page);
182 if (Assert.ASSERTS_ENABLED) {
183 Assert.that(page == (Page) addressToPageMap.get(pageBaseAddress),
184 "must have found page in cache!");
185 }
186 addPageToList(page);
187 // See whether eviction of oldest is necessary
188 if (numPages == maxNumPages) {
189 Page evictedPage = lruList.getPrev();
190 // System.err.println("-> Evicting page at 0x" + Long.toHexString(evictedPage.getBaseAddress()) +
191 // "; " + countPages() + " pages left (expect " + numPages + ")");
192 removePageFromList(evictedPage);
193 addressToPageMap.remove(evictedPage.getBaseAddress());
194 } else {
195 ++numPages;
196 }
197 }
198 } else {
199 // Page already in cache, move to front of list
200 removePageFromList(page);
201 addPageToList(page);
202 }
203 return page;
204 }
205
206 private Page checkPage(Page page, long startAddress) {
207 if (!page.isMapped()) {
208 throw new UnmappedAddressException(startAddress);
209 }
210 return page;
211 }
212
213 private int countPages() {
214 Page page = lruList;
215 int num = 0;
216 if (page == null) {
217 return num;
218 }
219 do {
220 ++num;
221 page = page.getNext();
222 } while (page != lruList);
223 return num;
224 }
225
226 private void flushPage(long pageBaseAddress) {
227 long key = pageBaseAddress;
228 Page page = (Page) addressToPageMap.remove(key);
229 if (page != null) {
230 removePageFromList(page);
231 }
232 }
233
234 // Adds given page to head of list
235 private void addPageToList(Page page) {
236 if (lruList == null) {
237 lruList = page;
238 page.setNext(page);
239 page.setPrev(page);
240 } else {
241 // Add to front of list
242 page.setNext(lruList);
243 page.setPrev(lruList.getPrev());
244 lruList.getPrev().setNext(page);
245 lruList.setPrev(page);
246 lruList = page;
247 }
248 }
249
250 // Removes given page from list
251 private void removePageFromList(Page page) {
252 if (page.getNext() == page) {
253 lruList = null;
254 } else {
255 if (lruList == page) {
256 lruList = page.getNext();
257 }
258 page.getPrev().setNext(page.getNext());
259 page.getNext().setPrev(page.getPrev());
260 }
261 page.setPrev(null);
262 page.setNext(null);
263 }
264
265 /** Ensure that page size fits within 32 bits and is a power of two, and that maxNumPages > 0 */
266 private void checkPageInfo(long pageSize, long maxNumPages) {
267 if ((pageSize <= 0) || maxNumPages <= 0) {
268 throw new IllegalArgumentException("pageSize and maxNumPages must both be greater than zero");
269 }
270 long tmpPageSize = pageSize >>> 32;
271 if (tmpPageSize != 0) {
272 throw new IllegalArgumentException("pageSize " + pageSize + " too big (must fit within 32 bits)");
273 }
274 int numNonZeroBits = 0;
275 for (int i = 0; i < 32; ++i) {
276 if ((pageSize & 1L) != 0) {
277 ++numNonZeroBits;
278 if ((numNonZeroBits > 1) || (i == 0)) {
279 throw new IllegalArgumentException("pageSize " + pageSize + " must be a power of two");
280 }
281 }
282 pageSize >>>= 1;
283 if (numNonZeroBits == 0) {
284 pageMask = (pageMask << 1) | 1L;
285 }
286 }
287 pageMask = ~pageMask;
288 }
289 }