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 protected final AddressArray currentBlock;
057
058 /****************************************************************************
059 *
060 * Initialization
061 */
062
063 /**
064 * Constructor
065 *
066 * @param space The space with which this allocator will be associated
067 */
068 public SegregatedFreeListLocal(S space) {
069 super(space);
070 this.currentBlock = AddressArray.create(space.sizeClassCount());
071 }
072
073 /****************************************************************************
074 *
075 * Allocation
076 */
077
078 /**
079 * Allocate <code>bytes</code> contiguous bytes of non-zeroed
080 * memory. First check if the fast path works. This is needed
081 * since this method may be called in the context when the fast
082 * version was NOT just called. If this fails, it will try finding
083 * another block with a non-empty free list, or allocating a new
084 * block.<p>
085 *
086 * This code should be relatively infrequently executed, so it is
087 * forced out of line to reduce pressure on the compilation of the
088 * core alloc routine.<p>
089 *
090 * Precondition: None
091 *
092 * Postconditions: A new cell has been allocated (not zeroed), and
093 * the block containing the cell has been placed on the appropriate
094 * free list data structures. The free list itself is not updated
095 * (the caller must do so).<p>
096 *
097 * @param bytes The size of the object to occupy this space, in bytes.
098 * @param offset The alignment offset.
099 * @param align The requested alignment.
100 * @return The address of the first word or zero on failure.
101 */
102 @NoInline
103 public final Address allocSlowOnce(int bytes, int align, int offset) {
104 // Did a collection occur and provide a free cell?
105 bytes = getMaximumAlignedSize(bytes, align);
106 int sizeClass = space.getSizeClass(bytes);
107 Address cell = freeList.get(sizeClass);
108
109 if (cell.isZero()) {
110 Address block = currentBlock.get(sizeClass);
111 if (!block.isZero()) {
112 // Return the block if we currently own one
113 space.returnConsumedBlock(block, sizeClass);
114 currentBlock.set(sizeClass, Address.zero());
115 }
116
117 // Get a new block for allocation, if returned, it is guaranteed to have a free cell
118 block = space.getAllocationBlock(sizeClass, freeList);
119
120 if (!block.isZero()) {
121 // We have a new current block and free list.
122 currentBlock.set(sizeClass, block);
123 cell = freeList.get(sizeClass);
124 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!cell.isZero());
125 } else {
126 // Allocation Failure
127 return Address.zero();
128 }
129 }
130
131 freeList.set(sizeClass, cell.loadAddress());
132 /* Clear the free list link */
133 cell.store(Address.zero());
134 return alignAllocation(cell, align, offset);
135 }
136
137 /****************************************************************************
138 *
139 * Preserving (saving & restoring) free lists
140 */
141
142 /**
143 * Zero all of the current free list pointers, and refresh the
144 * <code>currentBlock</code> values, so instead of the free list
145 * pointing to free cells, it points to the block containing the
146 * free cells. Then the free lists for each cell can be
147 * reestablished during GC. If the free lists are being preserved
148 * on a per-block basis (eager mark-sweep and reference counting),
149 * then free lists are remembered for each block.
150 */
151 public final void flush() {
152 for (int sizeClass = 0; sizeClass < space.sizeClassCount(); sizeClass++) {
153 Address block = currentBlock.get(sizeClass);
154 if (!block.isZero()) {
155 Address cell = freeList.get(sizeClass);
156 space.returnBlock(block, sizeClass, cell);
157 currentBlock.set(sizeClass, Address.zero());
158 freeList.set(sizeClass, Address.zero());
159 }
160 }
161 }
162 }