001 /*
002 * This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 * This file is licensed to You under the Eclipse Public License (EPL);
005 * You may not use this file except in compliance with the License. You
006 * may obtain a copy of the License at
007 *
008 * http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 * See the COPYRIGHT.txt file distributed with this work for information
011 * regarding copyright ownership.
012 */
013 package org.mmtk.utility.alloc;
014
015 import org.mmtk.policy.SegregatedFreeListSpace;
016 import org.mmtk.utility.*;
017
018 import org.mmtk.vm.VM;
019
020 import org.vmmagic.pragma.*;
021 import org.vmmagic.unboxed.*;
022
023 /**
024 * This abstract class implements a simple segregated free list.<p>
025 *
026 * See: Wilson, Johnstone, Neely and Boles "Dynamic Storage
027 * Allocation: A Survey and Critical Review", IWMM 1995, for an
028 * overview of free list allocation and the various implementation
029 * strategies, including segregated free lists.<p>
030 *
031 * We maintain a number of size classes, each size class having a free
032 * list of available objects of that size (the list may be empty). We
033 * call the storage elements "cells". Cells reside within chunks of
034 * memory called "blocks". All cells in a given block are of the same
035 * size (i.e. blocks are homogeneous with respect to size class).
036 * Each block maintains its own free list (free cells within that
037 * block). For each size class a list of blocks is maintained, one of
038 * which will serve the role of the current free list. When the free
039 * list on the current block is exhausted, the next block for that
040 * size class becomes the current block and its free list is used. If
041 * there are no more blocks the a new block is allocated.<p>
042 */
043 @Uninterruptible
044 public abstract class SegregatedFreeListLocal<S extends SegregatedFreeListSpace> extends SegregatedFreeList<S>
045 implements Constants {
046
047 /****************************************************************************
048 *
049 * Class variables
050 */
051
052 /****************************************************************************
053 *
054 * Instance variables
055 */
056
057 /**
058 *
059 */
060 protected final AddressArray currentBlock;
061
062 /****************************************************************************
063 *
064 * Initialization
065 */
066
067 /**
068 * Constructor
069 *
070 * @param space The space with which this allocator will be associated
071 */
072 public SegregatedFreeListLocal(S space) {
073 super(space);
074 this.currentBlock = AddressArray.create(space.sizeClassCount());
075 }
076
077 /****************************************************************************
078 *
079 * Allocation
080 */
081
082 /**
083 * Allocate <code>bytes</code> contiguous bytes of non-zeroed
084 * memory. First check if the fast path works. This is needed
085 * since this method may be called in the context when the fast
086 * version was NOT just called. If this fails, it will try finding
087 * another block with a non-empty free list, or allocating a new
088 * block.<p>
089 *
090 * This code should be relatively infrequently executed, so it is
091 * forced out of line to reduce pressure on the compilation of the
092 * core alloc routine.<p>
093 *
094 * Precondition: None<p>
095 *
096 * Postconditions: A new cell has been allocated (not zeroed), and
097 * the block containing the cell has been placed on the appropriate
098 * free list data structures. The free list itself is not updated
099 * (the caller must do so).<p>
100 *
101 * @param bytes The size of the object to occupy this space, in bytes.
102 * @param offset The alignment offset.
103 * @param align The requested alignment.
104 * @return The address of the first word or zero on failure.
105 */
106 @Override
107 @NoInline
108 public final Address allocSlowOnce(int bytes, int align, int offset) {
109 // Did a collection occur and provide a free cell?
110 bytes = getMaximumAlignedSize(bytes, align);
111 int sizeClass = space.getSizeClass(bytes);
112 Address cell = freeList.get(sizeClass);
113
114 if (cell.isZero()) {
115 Address block = currentBlock.get(sizeClass);
116 if (!block.isZero()) {
117 // Return the block if we currently own one
118 space.returnConsumedBlock(block, sizeClass);
119 currentBlock.set(sizeClass, Address.zero());
120 }
121
122 // Get a new block for allocation, if returned, it is guaranteed to have a free cell
123 block = space.getAllocationBlock(sizeClass, freeList);
124
125 if (!block.isZero()) {
126 // We have a new current block and free list.
127 currentBlock.set(sizeClass, block);
128 cell = freeList.get(sizeClass);
129 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!cell.isZero());
130 } else {
131 // Allocation Failure
132 return Address.zero();
133 }
134 }
135
136 freeList.set(sizeClass, cell.loadAddress());
137 /* Clear the free list link */
138 cell.store(Address.zero());
139 return alignAllocation(cell, align, offset);
140 }
141
142 /****************************************************************************
143 *
144 * Preserving (saving & restoring) free lists
145 */
146
147 /**
148 * Zero all of the current free list pointers, and refresh the
149 * <code>currentBlock</code> values, so instead of the free list
150 * pointing to free cells, it points to the block containing the
151 * free cells. Then the free lists for each cell can be
152 * reestablished during GC. If the free lists are being preserved
153 * on a per-block basis (eager mark-sweep and reference counting),
154 * then free lists are remembered for each block.
155 */
156 public final void flush() {
157 for (int sizeClass = 0; sizeClass < space.sizeClassCount(); sizeClass++) {
158 Address block = currentBlock.get(sizeClass);
159 if (!block.isZero()) {
160 Address cell = freeList.get(sizeClass);
161 space.returnBlock(block, sizeClass, cell);
162 currentBlock.set(sizeClass, Address.zero());
163 freeList.set(sizeClass, Address.zero());
164 }
165 }
166 }
167 }