1 /***********************************************************************/
2 /* Open Visualization Data Explorer */
3 /* (C) Copyright IBM Corp. 1989,1999 */
4 /* ALL RIGHTS RESERVED */
5 /* This code licensed under the */
6 /* "IBM PUBLIC LICENSE - Open Visualization Data Explorer" */
7 /***********************************************************************/
8
9 #include <dxconfig.h>
10
11
12 #define RECLAIM_TIMING 0
13
14 #include <stdio.h>
15 #include <stdlib.h>
16 #include <dx/dx.h>
17 #ifdef DXD_WIN
18 #include <sys/timeb.h>
19 #else
20 #include <sys/times.h>
21 #endif
22 #include "cache.h"
23 #include "graph.h"
24 #include "utils.h"
25 #include "swap.h"
26 #include "d.h"
27 #include "log.h"
28 #include "status.h"
29 #include "distp.h"
30
31 #define LOCK_REC() ( have_rec_sem++ ? OK : DXlock (rec_sem, 0))
32 #define UNLOCK_REC() (--have_rec_sem ? OK : DXunlock (rec_sem, 0))
33
34 static lock_type *rec_sem;
35
36 static int have_rec_sem = 0;
37 static EXO_Object rec_obj = NULL; /* for time stamp */
38 static int reclaiming_mem = 0;
39
40 extern int _dxd_exEnableDebug;
41
42 int
_dxf_ExReclaimingMemory()43 _dxf_ExReclaimingMemory()
44 {
45 return(reclaiming_mem);
46 }
47
48 /*
49 * (Un)locks the memory reclaimation so that other processors can't cause it
50 * to occur. This is necessary during some operations which assume that the
51 * cache is in a consistent state. We also set a local flag so that lower
52 * level library calls will not cause things to get thrown out of the cache.
53 * Note, that _dxf_ExReclaimDisable returns TRUE when someone else has
54 * been mucking with the cache, and may have freed memory, which caused us
55 * to wait.
56 */
57
58
59 int
_dxf_ExReclaimDisable()60 _dxf_ExReclaimDisable ()
61 {
62 int result;
63
64 if (have_rec_sem++)
65 return FALSE;
66
67 result = DXtry_lock(rec_sem, 0);
68 if (!result)
69 DXlock(rec_sem, 0);
70
71 return(!result);
72 }
73
74
_dxf_ExReclaimEnable()75 void _dxf_ExReclaimEnable ()
76 {
77 UNLOCK_REC ();
78 }
79
80
81 /*
82 * Initialize the cache memory scavenger.
83 */
84
85 static float factor = 1.0;
86
_dxf_ExInitMemoryReclaim()87 Error _dxf_ExInitMemoryReclaim ()
88 {
89 char *cp;
90
91 if ((rec_sem = (lock_type *) DXAllocate (sizeof (lock_type))) == NULL)
92 return (ERROR);
93
94 if (DXcreate_lock (rec_sem, "cache reclamation") != OK)
95 return (ERROR);
96
97 if ((rec_obj = (EXO_Object) DXAllocate (sizeof (exo_object))) == NULL)
98 return (ERROR);
99
100 rec_obj->lastref = 0.0;
101
102 if ((cp = getenv("DX_RECLAIM_FACTOR")) != NULL) {
103 factor = atof(cp);
104 if (factor <= 0.0 || factor >= 10.0)
105 factor = 1.0;
106 }
107
108 return (OK);
109 }
110
111 #if 0
112 cleanupMemoryReclaim()
113 {
114 DXdestroy_lock (rec_sem);
115 DXFree ((Pointer) rec_sem);
116 DXFree ((Pointer) rec_obj);
117 }
118 #endif
119
_dxf_ExSetGVarCost(gvar * gv,double cost)120 void _dxf_ExSetGVarCost(gvar *gv, double cost)
121 {
122 if (gv == NULL || gv->type == GV_UNRESOLVED)
123 return;
124
125 gv->cost = cost;
126 }
127
128 /*
129 * THE FIRST COMMENT IS VERY OLD AND DESCRIBES THE ORIGINAL BEHAVIOR
130 * OF THIS CODE. IT DOES NOT WORK LIKE THAT NOW. SEE THE SECOND
131 * PARAGRAPH FOR A MORE UP TO DATE PICTURE OF HOW THIS WORKS.
132 * (the description of the function it needs to perform is still valid;
133 * it's the approach to how it works which is much better now.)
134 *
135 * This is the cache memory scavenger. The global memory allocator calls
136 * this routine when it can't allocate a block of memory. 'nbytes' is the
137 * size of the block that the allocator needs to satisfy the request.
138 * This routine walks the cache and selects the ten best candidates for
139 * throwing away. Currently the selection is based only on the cost of
140 * creating the data stored in the cache entry. An obvious improvement
141 * would be to base the selection on the timestamp as well, so things which
142 * are frequently used will hang around for a while. Also the choice of
143 * ten items is pretty arbitrary and may be far from optimal.
144 *
145 * NEW NEW NEW
146 * first off, the timestamps on objects used to be the create time and
147 * not the time of last reference, so we could not do a real LRU algorithm
148 * even if we wanted to. this was fixed, so the timestamps are the last
149 * use. now we walk the cache in least-recently-used order, throwing
150 * away objects until we have enough space to hold the object we are
151 * trying to make space for. the memory manager was changed to bookkeep
152 * the size of the largest free block during cache scavenging, so this
153 * code no longer picks an arbitrary number of objects to delete.
154 *
155 */
156
157 #define N_PER_ITER 512
158
159 extern void DXInitMaxFreedBlock(); /* from libdx/memory.c */
160 extern ulong DXMaxFreedBlock(); /* from libdx/memory.c */
161
162 static int nDeleted;
163
164 static int
__ExReclaimMemory(ulong nbytes)165 __ExReclaimMemory (ulong nbytes)
166 {
167 EXObj obj;
168 gvar *gv;
169 int skipped;
170 char *key;
171 CacheTagList pkg;
172 uint32 *ctp;
173
174 _dxf_ExDictionaryBeginIterateSorted(_dxd_exCacheDict, 0);
175
176 pkg.numtags = 0;
177 ctp = pkg.ct;
178
179 while (NULL !=
180 (obj = _dxf_ExDictionaryIterateSorted(_dxd_exCacheDict, &key)))
181 {
182 gv = (gvar *)obj;
183
184 if (gv->type == GV_UNRESOLVED || gv->cost == CACHE_PERMANENT)
185 continue;
186
187 ExDebug ("2", "Free %s from cache", key);
188
189 if(key[0] == 'X') {
190 *ctp = strtoul(key+1, NULL, 16);
191 if (_dxf_ExDictionaryDelete (_dxd_exCacheDict, key) == OK)
192 {
193 pkg.numtags++;
194 ctp++;
195
196 if (pkg.numtags >= N_CACHETAGLIST_ITEMS)
197 {
198 _dxf_ExDistributeMsg(DM_EVICTCACHELIST, (Pointer)&pkg,
199 sizeof(CacheTagList), TOPEERS);
200 pkg.numtags = 0;
201 ctp = pkg.ct;
202 }
203 }
204 }
205 else
206 _dxf_ExDictionaryDelete(_dxd_exCacheDict, key);
207
208 nDeleted ++;
209
210 if (nbytes <= DXMaxFreedBlock())
211 break;
212 }
213
214 skipped = (obj) ? 1 : 0;
215
216 if(pkg.numtags > 0)
217 _dxf_ExDistributeMsg(DM_EVICTCACHELIST, (Pointer)&pkg,
218 sizeof(CacheTagList), TOPEERS);
219
220 _dxf_ExDictionaryEndIterate (_dxd_exCacheDict);
221
222 return skipped;
223 }
224
_dxf_ExReclaimMemory(ulong nbytes)225 int _dxf_ExReclaimMemory (ulong nbytes)
226 {
227 int status;
228 int found;
229
230 /*
231 * Sorry, the cache has to stay consistent for a while. Can't eject
232 * anything at the present time.
233 * Note, that if _dxf_ExReclaimDisable returns TRUE, then someone else has
234 * been mucking with the cache, and may have freed memory, go ahead
235 * and say there's more space.
236 */
237
238 #if RECLAIM_TIMING
239 DXMarkTimeLocal ("> RECLAIM");
240 #endif
241 if (_dxf_ExReclaimDisable ())
242 {
243 _dxf_ExReclaimEnable ();
244 return (TRUE);
245 }
246
247 reclaiming_mem = 1;
248
249 /*
250 * Get the last time this occurred if this is the first time then
251 * we need to initialize this for the entire system. So, let's
252 * assume that the last sweep just occurred.
253 */
254
255 DXDebug ("*0M", "Memory reclamation: looking for %lu bytes", nbytes);
256
257 status = get_status ();
258 set_status (PS_RECLAIM);
259
260 nDeleted = 0;
261
262 /*
263 * Now we run over the cache dictionary trying to delete something
264 * that gives us a block big enough.
265 */
266 DXInitMaxFreedBlock();
267
268 DXDebug ("M", " initial max free blocksize %lu bytes", DXMaxFreedBlock());
269
270 /*
271 * EXPERIMENT!! try reclaiming just a bit more than we need, and
272 * if we can't get it than try to get exactly what we do need. the
273 * idea is that we make larger holes in memory if we reclaim too much
274 * and perhaps delay fragementation by some amount.
275 */
276
277
278 /*
279 * ask for too much. if this fails, see if we got at least
280 * as much as we really need.
281 */
282 found = __ExReclaimMemory((ulong)(nbytes*factor));
283 if (found)
284 goto done;
285
286 DXDebug ("M", " after deleting %d items max blocksize now %lu",
287 nDeleted, DXMaxFreedBlock());
288 DXDebug ("M", " could not get %lu bytes (%g times %lu needed)",
289 (ulong)(nbytes*factor), factor, nbytes);
290
291 /*
292 * the first request looked at all objects which were valid to
293 * discard. there's no point in traversing the same list again.
294 * just look at the largest remaining block and see if it's big enough.
295 */
296 found = nbytes <= DXMaxFreedBlock();
297 if (found)
298 goto done;
299
300 DXDebug ("M", " going to try to compact dictionary");
301
302 /*
303 * If we still failed, clean up the dictionary and try again
304 */
305
306
307 if (_dxf_ExDictionaryCompact(_dxd_exCacheDict) ||
308 _dxf_ExGraphCompact() ||
309 _dxf_EXO_compact())
310 {
311 found = nbytes <= DXMaxFreedBlock();
312 if (! found)
313 found = __ExReclaimMemory(nbytes);
314 }
315
316 done:
317
318 DXDebug ("M", "deleted %d items, max blocksize now %lu, found=%d",
319 nDeleted, DXMaxFreedBlock(), found);
320
321 reclaiming_mem = 0;
322
323 _dxf_ExReclaimEnable ();
324
325 set_status (status);
326
327 return found;
328 }
329