001/* 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * http://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, 013 * software distributed under the License is distributed on an 014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 015 * KIND, either express or implied. See the License for the 016 * specific language governing permissions and limitations 017 * under the License. 018 * 019 */ 020package org.apache.directory.mavibot.btree; 021 022 023import java.util.ArrayList; 024import java.util.Arrays; 025import java.util.Iterator; 026import java.util.List; 027import java.util.Set; 028import java.util.TreeSet; 029 030import org.slf4j.Logger; 031import org.slf4j.LoggerFactory; 032 033 034/** 035 * A class used for reclaiming the copied pages. 036 * 037 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 038 */ 039public class PageReclaimer 040{ 041 /** the record manager */ 042 private RecordManager rm; 043 044 /** The LoggerFactory used by this class */ 045 protected static final Logger LOG = LoggerFactory.getLogger( PageReclaimer.class ); 046 047 /** a flag to detect the running state */ 048 private boolean running = false; 049 050 /** 051 * Creates a new instance of PageReclaimer. 052 * 053 * @param rm the record manager 054 */ 055 public PageReclaimer( RecordManager rm ) 056 { 057 this.rm = rm; 058 } 059 060 061 /** 062 * relcaims the copied pages 063 */ 064 /* no qualifier */ void reclaim() 065 { 066 //System.out.println( "reclaiming pages" ); 067 try 068 { 069 if ( running ) 070 { 071 return; 072 } 073 074 running = true; 075 076 Set<String> managed = rm.getManagedTrees(); 077 078 for ( String name : managed ) 079 { 080 PersistedBTree tree = ( PersistedBTree ) rm.getManagedTree( name ); 081 082 long latestRev = tree.getRevision(); 083 084 Set<Long> inUseRevisions = new TreeSet<Long>(); 085 086 // the tree might have been removed 087 if ( tree != null ) 088 { 089 Iterator<ReadTransaction> txnItr = tree.getReadTransactions().iterator(); 090 while ( txnItr.hasNext() ) 091 { 092 inUseRevisions.add( txnItr.next().getRevision() ); 093 } 094 } 095 096 List<RevisionOffset> copiedRevisions = getRevisions( name ); 097 098 // the revision last removed from copiedPage BTree 099 long lastRemovedRev = -1; 100 101 List<Long> freeList = new ArrayList<Long>(); 102 103 for ( RevisionOffset ro : copiedRevisions ) 104 { 105 long rv = ro.getRevision(); 106 if ( inUseRevisions.contains( rv ) ) 107 { 108 //System.out.println( "Revision " + rv + " of BTree " + name + " is in use, not reclaiming pages" ); 109 break; 110 } 111 112 long[] offsets = ro.getOffsets(); 113 114 //System.out.println( "Reclaiming " + Arrays.toString( offsets ) + "( " + offsets.length + " ) pages of the revision " + rv + " of BTree " + name ); 115 116 for( long l : offsets ) 117 { 118 freeList.add( l ); 119 } 120 121 RevisionName key = new RevisionName( rv, name ); 122 123 //System.out.println( "delete cpb key " + key ); 124 rm.copiedPageBtree.delete( key ); 125 lastRemovedRev = rv; 126 } 127 128 // no new txn is needed for the operations on BoB 129 // and also no need to traverse BoB if the tree is a sub-btree 130 if ( ( lastRemovedRev != -1 ) && !tree.isAllowDuplicates() ) 131 { 132 // we SHOULD NOT delete the latest revision from BoB 133 NameRevision nr = new NameRevision( name, latestRev ); 134 TupleCursor<NameRevision, Long> cursor = rm.btreeOfBtrees.browseFrom( nr ); 135 136 List<Long> btreeHeaderOffsets = new ArrayList<Long>(); 137 138 while ( cursor.hasPrev() ) 139 { 140 Tuple<NameRevision, Long> t = cursor.prev(); 141 //System.out.println( "deleting BoB rev " + t.getKey() + " latest rev " + latestRev ); 142 rm.btreeOfBtrees.delete( t.getKey() ); 143 btreeHeaderOffsets.add( t.value ); 144 } 145 146 cursor.close(); 147 148 for( Long l : btreeHeaderOffsets ) 149 { 150 // the offset may have already been present while 151 // clearing CPB so skip it here, otherwise it will result in OOM 152 // due to the attempt to free and already freed page 153 if(freeList.contains( l )) 154 { 155 //System.out.println( "bob duplicate offset " + l ); 156 continue; 157 } 158 159 freeList.add( l ); 160 } 161 } 162 163 for( Long offset : freeList ) 164 { 165 PageIO[] pageIos = rm.readPageIOs( offset, -1L ); 166 167 for ( PageIO pageIo : pageIos ) 168 { 169 rm.free( pageIo ); 170 } 171 } 172 173 } 174 175 running = false; 176 } 177 catch ( Exception e ) 178 { 179 running = false; 180 rm.rollback(); 181 LOG.warn( "Errors while reclaiming", e ); 182 throw new RuntimeException( e ); 183 } 184 } 185 186 187 /** 188 * gets a list of all the copied pages of a given B-Tree. 189 * 190 * @param name the name of the B-Tree 191 * @return list of RevisionOffset 192 * @throws Exception 193 */ 194 private List<RevisionOffset> getRevisions( String name ) throws Exception 195 { 196 TupleCursor<RevisionName, long[]> cursor = rm.copiedPageBtree.browse(); 197 198 List<RevisionOffset> lst = new ArrayList<RevisionOffset>(); 199 200 while ( cursor.hasNext() ) 201 { 202 Tuple<RevisionName, long[]> t = cursor.next(); 203 RevisionName rn = t.getKey(); 204 if ( name.equals( rn.getName() ) ) 205 { 206 //System.out.println( t.getValue() ); 207 lst.add( new RevisionOffset( rn.getRevision(), t.getValue() ) ); 208 } 209 } 210 211 cursor.close(); 212 213 return lst; 214 } 215}