Annotation of OpenXM_contrib/gc/allchblk.c, Revision 1.1.1.1
1.1 maekawa 1: /*
2: * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
3: * Copyright (c) 1991-1994 by Xerox Corporation. All rights reserved.
4: * Copyright (c) 1998 by Silicon Graphics. All rights reserved.
5: *
6: * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
7: * OR IMPLIED. ANY USE IS AT YOUR OWN RISK.
8: *
9: * Permission is hereby granted to use or copy this program
10: * for any purpose, provided the above notices are retained on all copies.
11: * Permission to modify the code and to distribute modified code is granted,
12: * provided the above notices are retained, and a notice that the code was
13: * modified is included with the above copyright notice.
14: */
15: /* Boehm, August 9, 1995 5:08 pm PDT */
16:
17: #define DEBUG
18: #undef DEBUG
19: #include <stdio.h>
20: #include "gc_priv.h"
21:
22:
23: /*
24: * allocate/free routines for heap blocks
25: * Note that everything called from outside the garbage collector
26: * should be prepared to abort at any point as the result of a signal.
27: */
28:
29: /*
30: * Free heap blocks are kept on a list sorted by address.
31: * The hb_hdr.hbh_sz field of a free heap block contains the length
32: * (in bytes) of the entire block.
33: * Neighbors are coalesced.
34: */
35:
36: # define MAX_BLACK_LIST_ALLOC (2*HBLKSIZE)
37: /* largest block we will allocate starting on a black */
38: /* listed block. Must be >= HBLKSIZE. */
39:
40: struct hblk * GC_hblkfreelist = 0;
41:
42: struct hblk *GC_savhbp = (struct hblk *)0; /* heap block preceding next */
43: /* block to be examined by */
44: /* GC_allochblk. */
45:
46: # if !defined(NO_DEBUGGING)
47: void GC_print_hblkfreelist()
48: {
49: struct hblk * h = GC_hblkfreelist;
50: word total_free = 0;
51: hdr * hhdr = HDR(h);
52: word sz;
53:
54: while (h != 0) {
55: sz = hhdr -> hb_sz;
56: GC_printf2("0x%lx size %lu ", (unsigned long)h, (unsigned long)sz);
57: total_free += sz;
58: if (GC_is_black_listed(h, HBLKSIZE) != 0) {
59: GC_printf0("start black listed\n");
60: } else if (GC_is_black_listed(h, hhdr -> hb_sz) != 0) {
61: GC_printf0("partially black listed\n");
62: } else {
63: GC_printf0("not black listed\n");
64: }
65: h = hhdr -> hb_next;
66: hhdr = HDR(h);
67: }
68: GC_printf1("Total of %lu bytes on free list\n", (unsigned long)total_free);
69: }
70:
71: # endif /* NO_DEBUGGING */
72:
73: /* Initialize hdr for a block containing the indicated size and */
74: /* kind of objects. */
75: /* Return FALSE on failure. */
76: static GC_bool setup_header(hhdr, sz, kind, flags)
77: register hdr * hhdr;
78: word sz; /* object size in words */
79: int kind;
80: unsigned char flags;
81: {
82: register word descr;
83:
84: /* Add description of valid object pointers */
85: if (!GC_add_map_entry(sz)) return(FALSE);
86: hhdr -> hb_map = GC_obj_map[sz > MAXOBJSZ? 0 : sz];
87:
88: /* Set size, kind and mark proc fields */
89: hhdr -> hb_sz = sz;
90: hhdr -> hb_obj_kind = kind;
91: hhdr -> hb_flags = flags;
92: descr = GC_obj_kinds[kind].ok_descriptor;
93: if (GC_obj_kinds[kind].ok_relocate_descr) descr += WORDS_TO_BYTES(sz);
94: hhdr -> hb_descr = descr;
95:
96: /* Clear mark bits */
97: GC_clear_hdr_marks(hhdr);
98:
99: hhdr -> hb_last_reclaimed = (unsigned short)GC_gc_no;
100: return(TRUE);
101: }
102:
103: #ifdef EXACT_FIRST
104: # define LAST_TRIP 2
105: #else
106: # define LAST_TRIP 1
107: #endif
108:
109: word GC_max_hblk_size = HBLKSIZE;
110:
111: /*
112: * Allocate (and return pointer to) a heap block
113: * for objects of size sz words.
114: *
115: * NOTE: We set obj_map field in header correctly.
116: * Caller is resposnsible for building an object freelist in block.
117: *
118: * We clear the block if it is destined for large objects, and if
119: * kind requires that newly allocated objects be cleared.
120: */
121: struct hblk *
122: GC_allochblk(sz, kind, flags)
123: word sz;
124: int kind;
125: unsigned char flags; /* IGNORE_OFF_PAGE or 0 */
126: {
127: register struct hblk *thishbp;
128: register hdr * thishdr; /* Header corr. to thishbp */
129: register struct hblk *hbp;
130: register hdr * hhdr; /* Header corr. to hbp */
131: struct hblk *prevhbp;
132: register hdr * phdr; /* Header corr. to prevhbp */
133: signed_word size_needed; /* number of bytes in requested objects */
134: signed_word size_avail; /* bytes available in this block */
135: int trip_count = 0;
136:
137: size_needed = HBLKSIZE * OBJ_SZ_TO_BLOCKS(sz);
138: if ((word)size_needed > GC_max_hblk_size)
139: GC_max_hblk_size = size_needed;
140:
141: /* search for a big enough block in free list */
142: hbp = GC_savhbp;
143: hhdr = HDR(hbp);
144: for(;;) {
145:
146: prevhbp = hbp;
147: phdr = hhdr;
148: hbp = (prevhbp == 0? GC_hblkfreelist : phdr->hb_next);
149: hhdr = HDR(hbp);
150:
151: if( prevhbp == GC_savhbp) {
152: if (trip_count == LAST_TRIP) return(0);
153: ++trip_count;
154: }
155:
156: if( hbp == 0 ) continue;
157:
158: size_avail = hhdr->hb_sz;
159: # ifdef EXACT_FIRST
160: if (trip_count <= 1 && size_avail != size_needed) continue;
161: # endif
162: if (size_avail < size_needed) continue;
163: # ifdef PRESERVE_LAST
164: if (size_avail != size_needed
165: && !GC_incremental
166: && (word)size_needed <= GC_max_hblk_size/2
167: && GC_in_last_heap_sect((ptr_t)hbp)
168: && GC_should_collect()) {
169: continue;
170: }
171: # endif
172: /* If the next heap block is obviously better, go on. */
173: /* This prevents us from disassembling a single large block */
174: /* to get tiny blocks. */
175: {
176: signed_word next_size;
177:
178: thishbp = hhdr -> hb_next;
179: if (thishbp == 0) thishbp = GC_hblkfreelist;
180: thishdr = HDR(thishbp);
181: next_size = (signed_word)(thishdr -> hb_sz);
182: if (next_size < size_avail
183: && next_size >= size_needed
184: && !GC_is_black_listed(thishbp, (word)size_needed)) {
185: continue;
186: }
187: }
188: if ( !IS_UNCOLLECTABLE(kind) &&
189: (kind != PTRFREE || size_needed > MAX_BLACK_LIST_ALLOC)) {
190: struct hblk * lasthbp = hbp;
191: ptr_t search_end = (ptr_t)hbp + size_avail - size_needed;
192: signed_word orig_avail = size_avail;
193: signed_word eff_size_needed = ((flags & IGNORE_OFF_PAGE)?
194: HBLKSIZE
195: : size_needed);
196:
197:
198: while ((ptr_t)lasthbp <= search_end
199: && (thishbp = GC_is_black_listed(lasthbp,
200: (word)eff_size_needed))) {
201: lasthbp = thishbp;
202: }
203: size_avail -= (ptr_t)lasthbp - (ptr_t)hbp;
204: thishbp = lasthbp;
205: if (size_avail >= size_needed) {
206: if (thishbp != hbp && GC_install_header(thishbp)) {
207: /* Split the block at thishbp */
208: thishdr = HDR(thishbp);
209: /* GC_invalidate_map not needed, since we will */
210: /* allocate this block. */
211: thishdr -> hb_next = hhdr -> hb_next;
212: thishdr -> hb_sz = size_avail;
213: hhdr -> hb_sz = (ptr_t)thishbp - (ptr_t)hbp;
214: hhdr -> hb_next = thishbp;
215: /* Advance to thishbp */
216: prevhbp = hbp;
217: phdr = hhdr;
218: hbp = thishbp;
219: hhdr = thishdr;
220: }
221: } else if (size_needed > (signed_word)BL_LIMIT
222: && orig_avail - size_needed
223: > (signed_word)BL_LIMIT) {
224: /* Punt, since anything else risks unreasonable heap growth. */
225: WARN("Needed to allocate blacklisted block at 0x%lx\n",
226: (word)hbp);
227: thishbp = hbp;
228: size_avail = orig_avail;
229: } else if (size_avail == 0
230: && size_needed == HBLKSIZE
231: && prevhbp != 0) {
232: # ifndef FIND_LEAK
233: static unsigned count = 0;
234:
235: /* The block is completely blacklisted. We need */
236: /* to drop some such blocks, since otherwise we spend */
237: /* all our time traversing them if pointerfree */
238: /* blocks are unpopular. */
239: /* A dropped block will be reconsidered at next GC. */
240: if ((++count & 3) == 0) {
241: /* Allocate and drop the block in small chunks, to */
242: /* maximize the chance that we will recover some */
243: /* later. */
244: struct hblk * limit = hbp + (hhdr->hb_sz/HBLKSIZE);
245: struct hblk * h;
246:
247: GC_words_wasted += hhdr->hb_sz;
248: phdr -> hb_next = hhdr -> hb_next;
249: for (h = hbp; h < limit; h++) {
250: if (h == hbp || GC_install_header(h)) {
251: hhdr = HDR(h);
252: (void) setup_header(
253: hhdr,
254: BYTES_TO_WORDS(HBLKSIZE - HDR_BYTES),
255: PTRFREE, 0); /* Cant fail */
256: if (GC_debugging_started) {
257: BZERO(hbp + HDR_BYTES, HBLKSIZE - HDR_BYTES);
258: }
259: }
260: }
261: /* Restore hbp to point at free block */
262: if (GC_savhbp == hbp) GC_savhbp = prevhbp;
263: hbp = prevhbp;
264: hhdr = phdr;
265: if (hbp == GC_savhbp) --trip_count;
266: }
267: # endif
268: }
269: }
270: if( size_avail >= size_needed ) {
271: /* found a big enough block */
272: /* let thishbp --> the block */
273: /* set prevhbp, hbp to bracket it */
274: thishbp = hbp;
275: thishdr = hhdr;
276: if( size_avail == size_needed ) {
277: hbp = hhdr->hb_next;
278: hhdr = HDR(hbp);
279: } else {
280: hbp = (struct hblk *)
281: (((word)thishbp) + size_needed);
282: if (!GC_install_header(hbp)) {
283: hbp = thishbp;
284: continue;
285: }
286: hhdr = HDR(hbp);
287: GC_invalidate_map(hhdr);
288: hhdr->hb_next = thishdr->hb_next;
289: hhdr->hb_sz = size_avail - size_needed;
290: }
291: /* remove *thishbp from hblk freelist */
292: if( prevhbp == 0 ) {
293: GC_hblkfreelist = hbp;
294: } else {
295: phdr->hb_next = hbp;
296: }
297: /* save current list search position */
298: GC_savhbp = hbp;
299: break;
300: }
301: }
302:
303: /* Notify virtual dirty bit implementation that we are about to write. */
304: GC_write_hint(thishbp);
305: /* This should deal better with large blocks. */
306:
307: /* Add it to map of valid blocks */
308: if (!GC_install_counts(thishbp, (word)size_needed)) return(0);
309: /* This leaks memory under very rare conditions. */
310:
311: /* Set up header */
312: if (!setup_header(thishdr, sz, kind, flags)) {
313: GC_remove_counts(thishbp, (word)size_needed);
314: return(0); /* ditto */
315: }
316:
317: /* Clear block if necessary */
318: if (GC_debugging_started
319: || sz > MAXOBJSZ && GC_obj_kinds[kind].ok_init) {
320: BZERO(thishbp + HDR_BYTES, size_needed - HDR_BYTES);
321: }
322:
323: /* We just successfully allocated a block. Restart count of */
324: /* consecutive failures. */
325: {
326: extern unsigned GC_fail_count;
327:
328: GC_fail_count = 0;
329: }
330:
331: return( thishbp );
332: }
333:
334: struct hblk * GC_freehblk_ptr = 0; /* Search position hint for GC_freehblk */
335:
336: /*
337: * Free a heap block.
338: *
339: * Coalesce the block with its neighbors if possible.
340: *
341: * All mark words are assumed to be cleared.
342: */
343: void
344: GC_freehblk(p)
345: register struct hblk *p;
346: {
347: register hdr *phdr; /* Header corresponding to p */
348: register struct hblk *hbp, *prevhbp;
349: register hdr *hhdr, *prevhdr;
350: register signed_word size;
351:
352: /* GC_savhbp may become invalid due to coalescing. Clear it. */
353: GC_savhbp = (struct hblk *)0;
354:
355: phdr = HDR(p);
356: size = phdr->hb_sz;
357: size = HBLKSIZE * OBJ_SZ_TO_BLOCKS(size);
358: GC_remove_counts(p, (word)size);
359: phdr->hb_sz = size;
360: GC_invalidate_map(phdr);
361: prevhbp = 0;
362:
363: /* The following optimization was suggested by David Detlefs. */
364: /* Note that the header cannot be NIL, since there cannot be an */
365: /* intervening call to GC_freehblk without resetting */
366: /* GC_freehblk_ptr. */
367: if (GC_freehblk_ptr != 0 &&
368: HDR(GC_freehblk_ptr)->hb_map == GC_invalid_map &&
369: (ptr_t)GC_freehblk_ptr < (ptr_t)p) {
370: hbp = GC_freehblk_ptr;
371: } else {
372: hbp = GC_hblkfreelist;
373: };
374: hhdr = HDR(hbp);
375:
376: while( (hbp != 0) && (hbp < p) ) {
377: prevhbp = hbp;
378: prevhdr = hhdr;
379: hbp = hhdr->hb_next;
380: hhdr = HDR(hbp);
381: }
382: GC_freehblk_ptr = prevhbp;
383:
384: /* Check for duplicate deallocation in the easy case */
385: if (hbp != 0 && (ptr_t)p + size > (ptr_t)hbp
386: || prevhbp != 0 && (ptr_t)prevhbp + prevhdr->hb_sz > (ptr_t)p) {
387: GC_printf1("Duplicate large block deallocation of 0x%lx\n",
388: (unsigned long) p);
389: GC_printf2("Surrounding free blocks are 0x%lx and 0x%lx\n",
390: (unsigned long) prevhbp, (unsigned long) hbp);
391: }
392:
393: /* Coalesce with successor, if possible */
394: if( (((word)p)+size) == ((word)hbp) ) {
395: phdr->hb_next = hhdr->hb_next;
396: phdr->hb_sz += hhdr->hb_sz;
397: GC_remove_header(hbp);
398: } else {
399: phdr->hb_next = hbp;
400: }
401:
402:
403: if( prevhbp == 0 ) {
404: GC_hblkfreelist = p;
405: } else if( (((word)prevhbp) + prevhdr->hb_sz)
406: == ((word)p) ) {
407: /* Coalesce with predecessor */
408: prevhdr->hb_next = phdr->hb_next;
409: prevhdr->hb_sz += phdr->hb_sz;
410: GC_remove_header(p);
411: } else {
412: prevhdr->hb_next = p;
413: }
414: }
415:
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to allchblk.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib / gc