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.io.BufferedReader; 024import java.io.File; 025import java.io.IOException; 026import java.io.InputStreamReader; 027import java.io.RandomAccessFile; 028import java.nio.BufferUnderflowException; 029import java.nio.ByteBuffer; 030import java.nio.channels.FileChannel; 031import java.util.ArrayList; 032import java.util.HashMap; 033import java.util.HashSet; 034import java.util.List; 035import java.util.Map; 036import java.util.Set; 037 038import org.apache.directory.mavibot.btree.exception.InvalidBTreeException; 039import org.apache.directory.mavibot.btree.serializer.ElementSerializer; 040import org.apache.directory.mavibot.btree.serializer.LongSerializer; 041import org.apache.directory.mavibot.btree.serializer.StringSerializer; 042import org.apache.directory.mavibot.btree.util.Strings; 043 044 045/** 046 * A class to examine a Mavibot database file. 047 * 048 * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a> 049 */ 050public class MavibotInspector 051{ 052 // The file to be read 053 private File dbFile; 054 055 // The recordManager 056 private static RecordManager rm; 057 058 private BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) ); 059 060 // The name of the two page arrays for the global file and teh free pages 061 private static final String GLOBAL_PAGES_NAME = "__global__"; 062 private static final String FREE_PAGES_NAME = "__free-pages__"; 063 064 // The set of page array we already know about 065 private static Set<String> knownPagesArrays = new HashSet<String>(); 066 067 // Create an array of pages to be checked for each B-tree, plus 068 // two others for the free pages and the global one 069 // We use one bit per page. It's 0 when the page 070 // hasn't been checked, 1 otherwise. 071 private static Map<String, int[]> checkedPages = new HashMap<String, int[]>(); 072 073 static 074 { 075 knownPagesArrays.add( GLOBAL_PAGES_NAME ); 076 knownPagesArrays.add( FREE_PAGES_NAME ); 077 knownPagesArrays.add( RecordManager.BTREE_OF_BTREES_NAME ); 078 knownPagesArrays.add( RecordManager.COPIED_PAGE_BTREE_NAME ); 079 } 080 081 082 /** 083 * A private class to store a few informations about a btree 084 * 085 086 private static BtreeInfo btreeInfo; 087 088 static 089 { 090 btreeInfo = new BtreeInfo(); 091 } 092 093 /** 094 * Create an instance of MavibotInspector 095 * @param dbFile The file to read 096 */ 097 public MavibotInspector( File dbFile ) 098 { 099 this.dbFile = dbFile; 100 } 101 102 103 /** 104 * Check that the file exists 105 */ 106 private boolean checkFilePresence() 107 { 108 if ( dbFile == null ) 109 { 110 System.out.println( "No mavibot database file was given" ); 111 return false; 112 } 113 114 if ( !dbFile.exists() ) 115 { 116 System.out.println( "Given mavibot database file " + dbFile + " doesn't exist" ); 117 return false; 118 } 119 120 return true; 121 } 122 123 124 /** 125 * Pretty print the file size 126 */ 127 public void printFileSize() throws IOException 128 { 129 FileChannel fileChannel = new RandomAccessFile( dbFile, "r" ).getChannel(); 130 131 long l = fileChannel.size(); 132 133 fileChannel.close(); 134 135 String msg; 136 137 if ( l < 1024 ) 138 { 139 msg = l + " bytes"; 140 } 141 else 142 { 143 msg = ( l / 1024 ) + " KB"; 144 } 145 146 System.out.println( msg ); 147 148 fileChannel.close(); 149 } 150 151 152 /** 153 * Print the number of B-trees 154 */ 155 public void printNumberOfBTrees() 156 { 157 int nbBtrees = 0; 158 159 if ( rm != null ) 160 { 161 nbBtrees = rm.getNbManagedTrees(); 162 } 163 164 // The number of trees. It must be at least 2 and > 0 165 System.out.println( "Total Number of BTrees: " + nbBtrees ); 166 } 167 168 169 /** 170 * Print the B-tree's name 171 */ 172 public void printBTreeNames() 173 { 174 if ( rm == null ) 175 { 176 System.out.println( "Couldn't find the number of managed btrees" ); 177 return; 178 } 179 180 Set<String> trees = rm.getManagedTrees(); 181 System.out.println( "\nManaged BTrees:" ); 182 183 for ( String tree : trees ) 184 { 185 System.out.println( tree ); 186 } 187 188 System.out.println(); 189 } 190 191 192 /** 193 * Check a B-tree 194 */ 195 public void inspectBTree() 196 { 197 if ( rm == null ) 198 { 199 System.out.println( "Cannot check BTree(s)" ); 200 return; 201 } 202 203 System.out.print( "BTree Name: " ); 204 String name = readLine(); 205 206 PersistedBTree<?, ?> pb = ( PersistedBTree<?, ?> ) rm.getManagedTree( name ); 207 208 if ( pb == null ) 209 { 210 System.out.println( "No BTree exists with the name '" + name + "'" ); 211 return; 212 } 213 214 System.out.println( "\nBTree offset: " + String.format( "0x%1$08x", pb.getBtreeOffset() ) ); 215 System.out.println( "BTree _info_ offset: " + String.format( "0x%1$08x", pb.getBtreeInfoOffset() ) ); 216 System.out.println( "BTree root page offset: " + String.format( "0x%1$08x", pb.getRootPageOffset() ) ); 217 System.out.println( "Number of elements present: " + pb.getNbElems() ); 218 System.out.println( "BTree Page size: " + pb.getPageSize() ); 219 System.out.println( "BTree revision: " + pb.getRevision() ); 220 System.out.println( "Key serializer: " + pb.getKeySerializerFQCN() ); 221 System.out.println( "Value serializer: " + pb.getValueSerializerFQCN() ); 222 System.out.println(); 223 } 224 225 226 /** 227 * Load the full fie into a new RecordManager 228 */ 229 private boolean loadRm() 230 { 231 try 232 { 233 if ( rm != null ) 234 { 235 System.out.println( "Closing record manager" ); 236 rm.close(); 237 } 238 239 rm = new RecordManager( dbFile.getAbsolutePath() ); 240 System.out.println( "Loaded record manager" ); 241 } 242 catch ( Exception e ) 243 { 244 System.out.println( "Given database file seems to be corrupted. " + e.getMessage() ); 245 return false; 246 } 247 248 return true; 249 } 250 251 252 /** 253 * Check the whole file 254 */ 255 /* no qualifier */static void check( RecordManager recordManager ) 256 { 257 try 258 { 259 rm = recordManager; 260 261 // First check the RMheader 262 ByteBuffer recordManagerHeader = ByteBuffer.allocate( RecordManager.RECORD_MANAGER_HEADER_SIZE ); 263 long fileSize = recordManager.fileChannel.size(); 264 265 if ( fileSize < RecordManager.RECORD_MANAGER_HEADER_SIZE ) 266 { 267 throw new InvalidBTreeException( "File size too small : " + fileSize ); 268 } 269 270 // Read the RMHeader 271 recordManager.fileChannel.read( recordManagerHeader, 0L ); 272 recordManagerHeader.flip(); 273 274 // The page size. It must be a power of 2, and above 16. 275 int pageSize = recordManagerHeader.getInt(); 276 277 if ( ( pageSize != recordManager.pageSize ) || ( pageSize < 32 ) 278 || ( ( pageSize & ( ~pageSize + 1 ) ) != pageSize ) ) 279 { 280 throw new InvalidBTreeException( "Wrong page size : " + pageSize ); 281 } 282 283 // Compute the number of pages in this file 284 long nbPages = ( fileSize - RecordManager.RECORD_MANAGER_HEADER_SIZE ) / pageSize; 285 286 // The number of trees. It must be at least >= 2 287 int nbBtrees = recordManagerHeader.getInt(); 288 289 if ( ( nbBtrees < 0 ) || ( nbBtrees != recordManager.nbBtree ) ) 290 { 291 throw new InvalidBTreeException( "Wrong nb trees : " + nbBtrees ); 292 } 293 294 // The first free page offset. It must be either -1 or below file size 295 // and its value must be a modulo of pageSize 296 long firstFreePage = recordManagerHeader.getLong(); 297 298 if ( firstFreePage != RecordManager.NO_PAGE ) 299 { 300 checkOffset( recordManager, firstFreePage ); 301 } 302 303 int nbPageBits = ( int ) ( nbPages / 32 ); 304 305 // The global page array 306 checkedPages.put( GLOBAL_PAGES_NAME, new int[nbPageBits + 1] ); 307 308 // The freePages array 309 checkedPages.put( FREE_PAGES_NAME, new int[nbPageBits + 1] ); 310 311 // The B-tree of B-trees array 312 checkedPages.put( RecordManager.BTREE_OF_BTREES_NAME, new int[nbPageBits + 1] ); 313 314 // Last, the Copied Pages B-tree array 315 checkedPages.put( RecordManager.COPIED_PAGE_BTREE_NAME, new int[nbPageBits + 1] ); 316 317 // Check the free files 318 checkFreePages( recordManager, checkedPages ); 319 320 // The B-trees offsets 321 long currentBtreeOfBtreesOffset = recordManagerHeader.getLong(); 322 long previousBtreeOfBtreesOffset = recordManagerHeader.getLong(); 323 long currentCopiedPagesBtreeOffset = recordManagerHeader.getLong(); 324 long previousCopiedPagesBtreeOffset = recordManagerHeader.getLong(); 325 326 // Check that the previous BOB offset is not pointing to something 327 if ( previousBtreeOfBtreesOffset != RecordManager.NO_PAGE ) 328 { 329 System.out.println( "The previous Btree of Btrees offset is not valid : " 330 + previousBtreeOfBtreesOffset ); 331 return; 332 } 333 334 // Check that the previous CPB offset is not pointing to something 335 if ( previousCopiedPagesBtreeOffset != RecordManager.NO_PAGE ) 336 { 337 System.out.println( "The previous Copied Pages Btree offset is not valid : " 338 + previousCopiedPagesBtreeOffset ); 339 return; 340 } 341 342 // Check that the current BOB offset is valid 343 checkOffset( recordManager, currentBtreeOfBtreesOffset ); 344 345 // Check that the current CPB offset is valid 346 checkOffset( recordManager, currentCopiedPagesBtreeOffset ); 347 348 // Now, check the BTree of Btrees 349 checkBtreeOfBtrees( recordManager, checkedPages ); 350 351 // And the Copied Pages BTree 352 checkBtree( recordManager, currentCopiedPagesBtreeOffset, checkedPages ); 353 354 // We can now dump the checked pages 355 dumpCheckedPages( recordManager, checkedPages ); 356 } 357 catch ( Exception e ) 358 { 359 // We catch the exception and rethrow it immediately to be able to 360 // put a breakpoint here 361 e.printStackTrace(); 362 throw new InvalidBTreeException( "Error : " + e.getMessage() ); 363 } 364 } 365 366 367 /** 368 * Check the Btree of Btrees 369 */ 370 private static <K, V> void checkBtreeOfBtrees( RecordManager recordManager, Map<String, int[]> checkedPages ) 371 throws Exception 372 { 373 // Read the BOB header 374 PageIO[] bobHeaderPageIos = recordManager 375 .readPageIOs( recordManager.currentBtreeOfBtreesOffset, Long.MAX_VALUE ); 376 377 // update the checkedPages 378 updateCheckedPages( checkedPages.get( RecordManager.BTREE_OF_BTREES_NAME ), recordManager.pageSize, 379 bobHeaderPageIos ); 380 updateCheckedPages( checkedPages.get( GLOBAL_PAGES_NAME ), recordManager.pageSize, bobHeaderPageIos ); 381 382 long dataPos = 0L; 383 384 // The B-tree current revision 385 recordManager.readLong( bobHeaderPageIos, dataPos ); 386 dataPos += RecordManager.LONG_SIZE; 387 388 // The nb elems in the tree 389 recordManager.readLong( bobHeaderPageIos, dataPos ); 390 dataPos += RecordManager.LONG_SIZE; 391 392 // The B-tree rootPage offset 393 long rootPageOffset = recordManager.readLong( bobHeaderPageIos, dataPos ); 394 395 checkOffset( recordManager, rootPageOffset ); 396 397 dataPos += RecordManager.LONG_SIZE; 398 399 // The B-tree info offset 400 long btreeInfoOffset = recordManager.readLong( bobHeaderPageIos, dataPos ); 401 402 checkOffset( recordManager, btreeInfoOffset ); 403 404 checkBtreeInfo( recordManager, checkedPages, btreeInfoOffset, -1L ); 405 406 // Check the elements in the btree itself 407 // We will read every single page 408 checkBtreeOfBtreesPage( recordManager, checkedPages, rootPageOffset ); 409 } 410 411 412 /** 413 * Check a user's B-tree 414 */ 415 private static <K, V> void checkBtree( RecordManager recordManager, long btreeOffset, 416 Map<String, int[]> checkedPages ) throws Exception 417 { 418 // Read the B-tree header 419 PageIO[] btreeHeaderPageIos = recordManager.readPageIOs( btreeOffset, Long.MAX_VALUE ); 420 421 long dataPos = 0L; 422 423 // The B-tree current revision 424 long btreeRevision = recordManager.readLong( btreeHeaderPageIos, dataPos ); 425 dataPos += RecordManager.LONG_SIZE; 426 427 // The nb elems in the tree 428 recordManager.readLong( btreeHeaderPageIos, dataPos ); 429 dataPos += RecordManager.LONG_SIZE; 430 431 // The B-tree rootPage offset 432 long rootPageOffset = recordManager.readLong( btreeHeaderPageIos, dataPos ); 433 434 checkOffset( recordManager, rootPageOffset ); 435 436 dataPos += RecordManager.LONG_SIZE; 437 438 // The B-tree info offset 439 long btreeInfoOffset = recordManager.readLong( btreeHeaderPageIos, dataPos ); 440 441 checkOffset( recordManager, btreeInfoOffset ); 442 443 BtreeInfo<K, V> btreeInfo = checkBtreeInfo( recordManager, checkedPages, btreeInfoOffset, btreeRevision ); 444 445 // Update the checked pages 446 updateCheckedPages( checkedPages.get( btreeInfo.btreeName ), recordManager.pageSize, btreeHeaderPageIos ); 447 updateCheckedPages( checkedPages.get( GLOBAL_PAGES_NAME ), recordManager.pageSize, btreeHeaderPageIos ); 448 449 // And now, process the rootPage 450 checkBtreePage( recordManager, btreeInfo, checkedPages, rootPageOffset ); 451 } 452 453 454 /** 455 * Check the Btree of Btrees rootPage 456 */ 457 private static <K, V> void checkBtreePage( RecordManager recordManager, BtreeInfo<K, V> btreeInfo, 458 Map<String, int[]> checkedPages, long pageOffset ) throws Exception 459 { 460 PageIO[] pageIos = recordManager.readPageIOs( pageOffset, Long.MAX_VALUE ); 461 462 // Update the checkedPages array 463 updateCheckedPages( checkedPages.get( btreeInfo.btreeName ), recordManager.pageSize, pageIos ); 464 updateCheckedPages( checkedPages.get( GLOBAL_PAGES_NAME ), recordManager.pageSize, pageIos ); 465 466 // Deserialize the page now 467 long position = 0L; 468 469 // The revision 470 long revision = recordManager.readLong( pageIos, position ); 471 position += RecordManager.LONG_SIZE; 472 473 // The number of elements in the page 474 int nbElems = recordManager.readInt( pageIos, position ); 475 position += RecordManager.INT_SIZE; 476 477 // The size of the data containing the keys and values 478 // Reads the bytes containing all the keys and values, if we have some 479 // We read big blob of data into ByteBuffer, then we will process 480 // this ByteBuffer 481 ByteBuffer byteBuffer = recordManager.readBytes( pageIos, position ); 482 483 // Now, deserialize the data block. If the number of elements 484 // is positive, it's a Leaf, otherwise it's a Node 485 // Note that only a leaf can have 0 elements, and it's the root page then. 486 if ( nbElems >= 0 ) 487 { 488 // It's a leaf, process it as we may have sub-btrees 489 checkBtreeLeaf( recordManager, btreeInfo, checkedPages, nbElems, revision, byteBuffer, pageIos ); 490 } 491 else 492 { 493 // It's a node 494 long[] children = checkBtreeNode( recordManager, btreeInfo, checkedPages, -nbElems, revision, byteBuffer, 495 pageIos ); 496 497 for ( int pos = 0; pos <= -nbElems; pos++ ) 498 { 499 // Recursively check the children 500 checkBtreePage( recordManager, btreeInfo, checkedPages, children[pos] ); 501 } 502 } 503 } 504 505 506 /** 507 * Check the Btree info page 508 * @throws ClassNotFoundException 509 */ 510 private static <K, V> BtreeInfo<K, V> checkBtreeInfo( RecordManager recordManager, Map<String, int[]> checkedPages, 511 long btreeInfoOffset, long btreeRevision ) throws IOException 512 { 513 BtreeInfo<K, V> btreeInfo = new BtreeInfo<K, V>(); 514 515 PageIO[] btreeInfoPagesIos = recordManager.readPageIOs( btreeInfoOffset, Long.MAX_VALUE ); 516 517 long dataPos = 0L; 518 519 // The B-tree page size 520 recordManager.readInt( btreeInfoPagesIos, dataPos ); 521 dataPos += RecordManager.INT_SIZE; 522 523 // The tree name 524 ByteBuffer btreeNameBytes = recordManager.readBytes( btreeInfoPagesIos, dataPos ); 525 dataPos += RecordManager.INT_SIZE + btreeNameBytes.limit(); 526 String btreeName = Strings.utf8ToString( btreeNameBytes ); 527 528 // The keySerializer FQCN 529 ByteBuffer keySerializerBytes = recordManager.readBytes( btreeInfoPagesIos, dataPos ); 530 531 if ( keySerializerBytes != null ) 532 { 533 String keySerializerFqcn = Strings.utf8ToString( keySerializerBytes ); 534 535 btreeInfo.keySerializer = getSerializer( keySerializerFqcn ); 536 } 537 538 dataPos += RecordManager.INT_SIZE + keySerializerBytes.limit(); 539 540 // The valueSerialier FQCN 541 ByteBuffer valueSerializerBytes = recordManager.readBytes( btreeInfoPagesIos, dataPos ); 542 543 if ( valueSerializerBytes != null ) 544 { 545 String valueSerializerFqcn = Strings.utf8ToString( valueSerializerBytes ); 546 547 btreeInfo.valueSerializer = getSerializer( valueSerializerFqcn ); 548 } 549 550 dataPos += RecordManager.INT_SIZE + valueSerializerBytes.limit(); 551 552 // The B-tree allowDuplicates flag 553 recordManager.readInt( btreeInfoPagesIos, dataPos ); 554 dataPos += RecordManager.INT_SIZE; 555 556 // update the checkedPages 557 if ( !RecordManager.COPIED_PAGE_BTREE_NAME.equals( btreeName ) 558 && !RecordManager.BTREE_OF_BTREES_NAME.equals( btreeName ) ) 559 { 560 //btreeName = btreeName + "<" + btreeRevision + ">"; 561 } 562 563 btreeInfo.btreeName = btreeName; 564 565 // Update the checkedPages 566 int[] checkedPagesArray = checkedPages.get( btreeName ); 567 568 if ( checkedPagesArray == null ) 569 { 570 // Add the new name in the checkedPage name if it's not already there 571 checkedPagesArray = createPageArray( recordManager ); 572 checkedPages.put( btreeName, checkedPagesArray ); 573 } 574 575 updateCheckedPages( checkedPagesArray, recordManager.pageSize, btreeInfoPagesIos ); 576 updateCheckedPages( checkedPages.get( GLOBAL_PAGES_NAME ), recordManager.pageSize, btreeInfoPagesIos ); 577 578 return btreeInfo; 579 } 580 581 582 /** 583 * Get back the serializer instance 584 */ 585 @SuppressWarnings("unchecked") 586 private static <T> ElementSerializer<T> getSerializer( String serializerFqcn ) 587 { 588 try 589 { 590 Class<?> serializerClass = Class.forName( serializerFqcn ); 591 ElementSerializer<T> serializer = null; 592 593 try 594 { 595 serializer = ( ElementSerializer<T> ) serializerClass.getDeclaredField( "INSTANCE" ).get( null ); 596 } 597 catch ( NoSuchFieldException e ) 598 { 599 // ignore 600 } 601 602 if ( serializer == null ) 603 { 604 serializer = ( ElementSerializer<T> ) serializerClass.newInstance(); 605 } 606 607 return serializer; 608 } 609 catch ( Exception e ) 610 { 611 throw new InvalidBTreeException( "Error : " + e.getMessage() ); 612 } 613 } 614 615 616 /** 617 * Check the Btree of Btrees rootPage 618 */ 619 private static <K, V> void checkBtreeOfBtreesPage( RecordManager recordManager, Map<String, int[]> checkedPages, 620 long pageOffset ) throws Exception 621 { 622 PageIO[] pageIos = recordManager.readPageIOs( pageOffset, Long.MAX_VALUE ); 623 624 // Update the checkedPages array 625 updateCheckedPages( checkedPages.get( RecordManager.BTREE_OF_BTREES_NAME ), recordManager.pageSize, pageIos ); 626 updateCheckedPages( checkedPages.get( GLOBAL_PAGES_NAME ), recordManager.pageSize, pageIos ); 627 628 // Deserialize the page now 629 long position = 0L; 630 631 // The revision 632 long revision = recordManager.readLong( pageIos, position ); 633 position += RecordManager.LONG_SIZE; 634 635 // The number of elements in the page 636 int nbElems = recordManager.readInt( pageIos, position ); 637 position += RecordManager.INT_SIZE; 638 639 // The size of the data containing the keys and values 640 // Reads the bytes containing all the keys and values, if we have some 641 // We read big blob of data into ByteBuffer, then we will process 642 // this ByteBuffer 643 ByteBuffer byteBuffer = recordManager.readBytes( pageIos, position ); 644 645 // Now, deserialize the data block. If the number of elements 646 // is positive, it's a Leaf, otherwise it's a Node 647 // Note that only a leaf can have 0 elements, and it's the root page then. 648 if ( nbElems >= 0 ) 649 { 650 // It's a leaf, process it as we may have sub-btrees 651 checkBtreeOfBtreesLeaf( recordManager, checkedPages, nbElems, revision, byteBuffer, pageIos ); 652 } 653 else 654 { 655 // It's a node 656 long[] children = checkBtreeOfBtreesNode( recordManager, checkedPages, -nbElems, revision, byteBuffer, 657 pageIos ); 658 659 for ( int pos = 0; pos <= -nbElems; pos++ ) 660 { 661 // Recursively check the children 662 checkBtreeOfBtreesPage( recordManager, checkedPages, children[pos] ); 663 } 664 } 665 } 666 667 668 /** 669 * Check a Btree of Btrees leaf. It contains <revision, name> -> offset. 670 */ 671 private static <K, V> void checkBtreeOfBtreesLeaf( RecordManager recordManager, Map<String, int[]> checkedPages, 672 int nbElems, long revision, ByteBuffer byteBuffer, PageIO[] pageIos ) throws Exception 673 { 674 // Read each key and value 675 for ( int i = 0; i < nbElems; i++ ) 676 { 677 try 678 { 679 // Read the number of values 680 int nbValues = byteBuffer.getInt(); 681 682 if ( nbValues != 1 ) 683 { 684 throw new InvalidBTreeException( "We should have only one value for a BOB " + nbValues ); 685 } 686 687 // This is a normal value 688 // First, the value, which is an offset, which length should be 12 689 int valueLength = byteBuffer.getInt(); 690 691 if ( valueLength != RecordManager.LONG_SIZE + RecordManager.INT_SIZE ) 692 { 693 throw new InvalidBTreeException( "The BOB value length is invalid " + valueLength ); 694 } 695 696 // Second, the offset length, which should be 8 697 int offsetLength = byteBuffer.getInt(); 698 699 if ( offsetLength != RecordManager.LONG_SIZE ) 700 { 701 throw new InvalidBTreeException( "The BOB value offset length is invalid " + offsetLength ); 702 } 703 704 // Then the offset 705 long btreeOffset = byteBuffer.getLong(); 706 707 checkOffset( recordManager, btreeOffset ); 708 709 // Now, process the key 710 // First the key length 711 int keyLength = byteBuffer.getInt(); 712 713 // The length should be at least 12 bytes long 714 if ( keyLength < RecordManager.LONG_SIZE + RecordManager.INT_SIZE ) 715 { 716 throw new InvalidBTreeException( "The BOB key length is invalid " + keyLength ); 717 } 718 719 // Read the revision 720 long btreeRevision = byteBuffer.getLong(); 721 722 // read the btreeName 723 int btreeNameLength = byteBuffer.getInt(); 724 725 // The length should be equals to the btreeRevision + btreeNameLength + 4 726 if ( keyLength != RecordManager.LONG_SIZE + RecordManager.INT_SIZE + btreeNameLength ) 727 { 728 throw new InvalidBTreeException( "The BOB key length is not the expected value " + 729 ( RecordManager.LONG_SIZE + RecordManager.INT_SIZE + btreeNameLength ) + ", expected " 730 + keyLength ); 731 } 732 733 byte[] bytes = new byte[btreeNameLength]; 734 byteBuffer.get( bytes ); 735 String btreeName = Strings.utf8ToString( bytes ); 736 737 // Add the new name in the checkedPage name if it's not already there 738 int[] btreePagesArray = createPageArray( recordManager ); 739 checkedPages.put( btreeName, btreePagesArray ); 740 741 // Now, we can check the Btree we just found 742 checkBtree( recordManager, btreeOffset, checkedPages ); 743 744 //System.out.println( "read <" + btreeName + "," + btreeRevision + "> : 0x" + Long.toHexString( btreeOffset ) ); 745 } 746 catch ( BufferUnderflowException bue ) 747 { 748 throw new InvalidBTreeException( "The BOB leaf byte buffer is too short : " + bue.getMessage() ); 749 } 750 } 751 } 752 753 754 /** 755 * Check a Btree leaf. 756 */ 757 private static <K, V> void checkBtreeLeaf( RecordManager recordManager, BtreeInfo<K, V> btreeInfo, 758 Map<String, int[]> checkedPages, int nbElems, long revision, ByteBuffer byteBuffer, PageIO[] pageIos ) 759 throws Exception 760 { 761 // Read each key and value 762 for ( int i = 0; i < nbElems; i++ ) 763 { 764 try 765 { 766 // Read the number of values 767 int nbValues = byteBuffer.getInt(); 768 769 if ( nbValues < 0 ) 770 { 771 // This is a sub-btree. Read the offset 772 long subBtreeOffset = byteBuffer.getLong(); 773 774 // And process the sub-btree 775 checkBtree( recordManager, subBtreeOffset, checkedPages ); 776 777 // Now, process the key 778 // The key length 779 byteBuffer.getInt(); 780 781 // The key itself 782 btreeInfo.keySerializer.deserialize( byteBuffer ); 783 } 784 else 785 { 786 // just deserialize the keys and values 787 // The value 788 byteBuffer.getInt(); 789 btreeInfo.valueSerializer.deserialize( byteBuffer ); 790 791 // the key 792 byteBuffer.getInt(); 793 794 btreeInfo.keySerializer.deserialize( byteBuffer ); 795 } 796 } 797 catch ( BufferUnderflowException bue ) 798 { 799 throw new InvalidBTreeException( "The BOB leaf byte buffer is too short : " + bue.getMessage() ); 800 } 801 } 802 } 803 804 805 /** 806 * Check a Btree of Btrees Node 807 */ 808 private static <K, V> long[] checkBtreeOfBtreesNode( RecordManager recordManager, Map<String, int[]> checkedPages, 809 int nbElems, long revision, 810 ByteBuffer byteBuffer, PageIO[] pageIos ) throws IOException 811 { 812 long[] children = new long[nbElems + 1]; 813 814 // Read each value 815 for ( int i = 0; i < nbElems; i++ ) 816 { 817 // The offsets of the child 818 long firstOffset = LongSerializer.INSTANCE.deserialize( byteBuffer ); 819 820 checkOffset( recordManager, firstOffset ); 821 822 long lastOffset = LongSerializer.INSTANCE.deserialize( byteBuffer ); 823 824 checkOffset( recordManager, lastOffset ); 825 826 children[i] = firstOffset; 827 828 // Read the key length 829 int keyLength = byteBuffer.getInt(); 830 831 // The length should be at least 12 bytes long 832 if ( keyLength < RecordManager.LONG_SIZE + RecordManager.INT_SIZE ) 833 { 834 throw new InvalidBTreeException( "The BOB key length is invalid " + keyLength ); 835 } 836 837 // Read the revision 838 byteBuffer.getLong(); 839 840 // read the btreeName 841 int btreeNameLength = byteBuffer.getInt(); 842 843 // The length should be equals to the btreeRevision + btreeNameLength + 4 844 if ( keyLength != RecordManager.LONG_SIZE + RecordManager.INT_SIZE + btreeNameLength ) 845 { 846 throw new InvalidBTreeException( "The BOB key length is not the expected value " + 847 ( RecordManager.LONG_SIZE + RecordManager.INT_SIZE + btreeNameLength ) + ", expected " + keyLength ); 848 } 849 850 // Read the Btree name 851 byte[] bytes = new byte[btreeNameLength]; 852 byteBuffer.get( bytes ); 853 } 854 855 // And read the last child 856 // The offsets of the child 857 long firstOffset = LongSerializer.INSTANCE.deserialize( byteBuffer ); 858 859 checkOffset( recordManager, firstOffset ); 860 861 long lastOffset = LongSerializer.INSTANCE.deserialize( byteBuffer ); 862 863 checkOffset( recordManager, lastOffset ); 864 865 children[nbElems] = firstOffset; 866 867 // and read the last value, as it's a node 868 return children; 869 } 870 871 872 /** 873 * Check a Btree node. 874 */ 875 private static <K, V> long[] checkBtreeNode( RecordManager recordManager, BtreeInfo<K, V> btreeInfo, 876 Map<String, int[]> checkedPages, int nbElems, long revision, ByteBuffer byteBuffer, PageIO[] pageIos ) 877 throws Exception 878 { 879 long[] children = new long[nbElems + 1]; 880 881 // Read each key and value 882 for ( int i = 0; i < nbElems; i++ ) 883 { 884 try 885 { 886 // The offsets of the child 887 long firstOffset = LongSerializer.INSTANCE.deserialize( byteBuffer ); 888 889 checkOffset( recordManager, firstOffset ); 890 891 long lastOffset = LongSerializer.INSTANCE.deserialize( byteBuffer ); 892 893 checkOffset( recordManager, lastOffset ); 894 895 children[i] = firstOffset; 896 897 // Now, read the key 898 // The key lenth 899 byteBuffer.getInt(); 900 901 // The key itself 902 btreeInfo.keySerializer.deserialize( byteBuffer ); 903 } 904 catch ( BufferUnderflowException bue ) 905 { 906 throw new InvalidBTreeException( "The BOB leaf byte buffer is too short : " + bue.getMessage() ); 907 } 908 } 909 910 // The last child 911 // The offsets of the child 912 long firstOffset = LongSerializer.INSTANCE.deserialize( byteBuffer ); 913 914 checkOffset( recordManager, firstOffset ); 915 916 long lastOffset = LongSerializer.INSTANCE.deserialize( byteBuffer ); 917 918 checkOffset( recordManager, lastOffset ); 919 920 children[nbElems] = firstOffset; 921 922 return children; 923 } 924 925 926 /** 927 * Create an array of bits for pages 928 */ 929 private static int[] createPageArray( RecordManager recordManager ) throws IOException 930 { 931 long fileSize = recordManager.fileChannel.size(); 932 int pageSize = recordManager.pageSize; 933 long nbPages = ( fileSize - RecordManager.RECORD_MANAGER_HEADER_SIZE ) / pageSize; 934 int nbPageBits = ( int ) ( nbPages / 32 ); 935 936 return new int[nbPageBits + 1]; 937 } 938 939 940 /** 941 * Update the array of seen pages. 942 */ 943 private static void updateCheckedPages( int[] checkedPages, int pageSize, PageIO... pageIos ) 944 { 945 for ( PageIO pageIO : pageIos ) 946 { 947 long offset = pageIO.getOffset(); 948 949 setCheckedPage( rm, checkedPages, offset ); 950 } 951 } 952 953 954 /** 955 * Check the offset to be sure it's a valid one : 956 * <ul> 957 * <li>It's >= 0</li> 958 * <li>It's below the end of the file</li> 959 * <li>It's a multiple of the pageSize 960 * </ul> 961 */ 962 private static void checkOffset( RecordManager recordManager, long offset ) throws IOException 963 { 964 if ( ( offset == RecordManager.NO_PAGE ) || 965 ( ( ( offset - RecordManager.RECORD_MANAGER_HEADER_SIZE ) % recordManager.pageSize ) != 0 ) || 966 ( offset > recordManager.fileChannel.size() ) ) 967 { 968 throw new InvalidBTreeException( "Invalid Offset : " + offset ); 969 } 970 } 971 972 973 /** 974 * Check the free pages 975 */ 976 private static void checkFreePages( RecordManager recordManager, Map<String, int[]> checkedPages ) 977 throws IOException 978 { 979 if ( recordManager.firstFreePage == RecordManager.NO_PAGE ) 980 { 981 return; 982 } 983 984 // Now, read all the free pages 985 long currentOffset = recordManager.firstFreePage; 986 long fileSize = recordManager.fileChannel.size(); 987 988 while ( currentOffset != RecordManager.NO_PAGE ) 989 { 990 if ( currentOffset > fileSize ) 991 { 992 System.out.println( "Wrong free page offset, above file size : " + currentOffset ); 993 return; 994 } 995 996 try 997 { 998 PageIO pageIo = recordManager.fetchPage( currentOffset ); 999 1000 if ( currentOffset != pageIo.getOffset() ) 1001 { 1002 System.out.println( "PageIO offset is incorrect : " + currentOffset + "-" 1003 + pageIo.getOffset() ); 1004 return; 1005 } 1006 1007 setCheckedPage( recordManager, checkedPages.get( GLOBAL_PAGES_NAME ), currentOffset ); 1008 setCheckedPage( recordManager, checkedPages.get( FREE_PAGES_NAME ), currentOffset ); 1009 1010 long newOffset = pageIo.getNextPage(); 1011 currentOffset = newOffset; 1012 } 1013 catch ( IOException ioe ) 1014 { 1015 throw new InvalidBTreeException( "Cannot fetch page at : " + currentOffset ); 1016 } 1017 } 1018 } 1019 1020 1021 /** 1022 * Update the ChekcedPages array 1023 */ 1024 private static void setCheckedPage( RecordManager recordManager, int[] checkedPages, long offset ) 1025 { 1026 int pageNumber = ( int ) offset / recordManager.pageSize; 1027 int nbBitsPage = ( RecordManager.INT_SIZE << 3 ); 1028 long pageMask = checkedPages[pageNumber / nbBitsPage]; 1029 long mask = 1L << pageNumber % nbBitsPage; 1030 1031 if ( ( pageMask & mask ) != 0 ) 1032 { 1033 //throw new InvalidBTreeException( "The page " + offset + " has already been referenced" ); 1034 } 1035 1036 pageMask |= mask; 1037 1038 checkedPages[pageNumber / nbBitsPage] |= pageMask; 1039 } 1040 1041 1042 /** 1043 * Output the pages that has been seen ('1') and those which has not been seen ('0'). The '.' represent non-pages 1044 * at the end of the file. 1045 */ 1046 private static void dumpCheckedPages( RecordManager recordManager, Map<String, int[]> checkedPages ) 1047 throws IOException 1048 { 1049 // First dump the global array 1050 int[] globalArray = checkedPages.get( GLOBAL_PAGES_NAME ); 1051 String result = dumpPageArray( recordManager, globalArray ); 1052 1053 String dump = String.format( "%1$-40s : %2$s", GLOBAL_PAGES_NAME, result ); 1054 System.out.println( dump ); 1055 1056 // The free pages array 1057 int[] freePagesArray = checkedPages.get( FREE_PAGES_NAME ); 1058 result = dumpPageArray( recordManager, freePagesArray ); 1059 1060 dump = String.format( "%1$-40s : %2$s", FREE_PAGES_NAME, result ); 1061 System.out.println( dump ); 1062 1063 // The B-tree of B-trees pages array 1064 int[] btreeOfBtreesArray = checkedPages.get( RecordManager.BTREE_OF_BTREES_NAME ); 1065 result = dumpPageArray( recordManager, btreeOfBtreesArray ); 1066 1067 dump = String.format( "%1$-40s : %2$s", RecordManager.BTREE_OF_BTREES_NAME, result ); 1068 System.out.println( dump ); 1069 1070 // The Copied page B-tree pages array 1071 int[] copiedPagesArray = checkedPages.get( RecordManager.COPIED_PAGE_BTREE_NAME ); 1072 result = dumpPageArray( recordManager, copiedPagesArray ); 1073 1074 dump = String.format( "%1$-40s : %2$s", RecordManager.COPIED_PAGE_BTREE_NAME, result ); 1075 System.out.println( dump ); 1076 1077 // And now, all the other btree arrays 1078 for ( String btreeName : checkedPages.keySet() ) 1079 { 1080 // Don't do the array we have already processed 1081 if ( knownPagesArrays.contains( btreeName ) ) 1082 { 1083 continue; 1084 } 1085 1086 int[] btreePagesArray = checkedPages.get( btreeName ); 1087 result = dumpPageArray( recordManager, btreePagesArray ); 1088 1089 dump = String.format( "%1$-40s : %2$s", btreeName, result ); 1090 System.out.println( dump ); 1091 } 1092 } 1093 1094 1095 /** 1096 * @see #getPageOffsets() 1097 */ 1098 public static List<Long> getFreePages() throws IOException 1099 { 1100 return getPageOffsets( FREE_PAGES_NAME ); 1101 } 1102 1103 1104 /** 1105 * @see #getPageOffsets() 1106 */ 1107 public static List<Long> getGlobalPages() throws IOException 1108 { 1109 return getPageOffsets( GLOBAL_PAGES_NAME ); 1110 } 1111 1112 1113 /** 1114 * Gives a list of offsets of pages from the page array associated wit the given name. 1115 * 1116 * This method should always be called after calling check() method. 1117 * 1118 * @return a list of offsets 1119 * @throws IOException 1120 */ 1121 public static List<Long> getPageOffsets( String pageArrayName ) throws IOException 1122 { 1123 List<Long> lst = new ArrayList<Long>(); 1124 1125 int[] fparry = checkedPages.get( pageArrayName ); 1126 1127 long nbPagesChecked = 0; // the 0th page will always be of RM header 1128 long fileSize = rm.fileChannel.size(); 1129 long nbPages = ( fileSize - RecordManager.RECORD_MANAGER_HEADER_SIZE ) / rm.pageSize; 1130 1131 for ( int checkedPage : fparry ) 1132 { 1133 for ( int j = 0; j < 32; j++ ) 1134 { 1135 1136 if ( nbPagesChecked > nbPages + 1 ) 1137 { 1138 break; 1139 } 1140 else 1141 { 1142 int mask = ( checkedPage & ( 1 << j ) ); 1143 if ( mask != 0 ) 1144 { 1145 lst.add( nbPagesChecked * rm.pageSize); 1146 } 1147 } 1148 1149 nbPagesChecked++; 1150 } 1151 } 1152 1153 return lst; 1154 } 1155 1156 1157 /** 1158 * Process a page array 1159 */ 1160 private static String dumpPageArray( RecordManager recordManager, int[] checkedPages ) throws IOException 1161 { 1162 StringBuilder sb = new StringBuilder(); 1163 int i = -1; 1164 int nbPagesChecked = 0; 1165 long fileSize = recordManager.fileChannel.size(); 1166 long nbPages = ( fileSize - RecordManager.RECORD_MANAGER_HEADER_SIZE ) / recordManager.pageSize; 1167 1168 for ( int checkedPage : checkedPages ) 1169 { 1170 if ( i == 0 ) 1171 { 1172 sb.append( " " ); 1173 i++; 1174 } 1175 else 1176 { 1177 i = 0; 1178 } 1179 1180 sb.append( "[" ).append( i ).append( "] " ); 1181 1182 for ( int j = 0; j < 32; j++ ) 1183 { 1184 if ( nbPagesChecked >= nbPages + 1 ) 1185 { 1186 sb.append( "." ); 1187 } 1188 else 1189 { 1190 if ( ( checkedPage & ( 1 << j ) ) == 0 ) 1191 { 1192 sb.append( "0" ); 1193 } 1194 else 1195 { 1196 sb.append( "1" ); 1197 } 1198 } 1199 1200 nbPagesChecked++; 1201 } 1202 } 1203 1204 return sb.toString(); 1205 } 1206 1207 1208 /** 1209 * The entry point method 1210 */ 1211 public void start() throws Exception 1212 { 1213 if ( !checkFilePresence() ) 1214 { 1215 return; 1216 } 1217 1218 if ( !loadRm() ) 1219 { 1220 return; 1221 } 1222 1223 boolean stop = false; 1224 1225 while ( !stop ) 1226 { 1227 System.out.println( "Choose an option:" ); 1228 System.out.println( "n - Print Number of BTrees" ); 1229 System.out.println( "b - Print BTree Names" ); 1230 System.out.println( "i - Inspect BTree" ); 1231 System.out.println( "c - Check Free Pages" ); 1232 System.out.println( "s - Get database file size" ); 1233 System.out.println( "d - Dump RecordManager" ); 1234 System.out.println( "r - Reload RecordManager" ); 1235 System.out.println( "o - Read page at offset" ); 1236 System.out.println( "q - Quit" ); 1237 1238 char c = readOption(); 1239 1240 switch ( c ) 1241 { 1242 case 'n': 1243 printNumberOfBTrees(); 1244 break; 1245 1246 case 'b': 1247 printBTreeNames(); 1248 break; 1249 1250 case 'i': 1251 inspectBTree(); 1252 break; 1253 1254 case 'c': 1255 long fileSize = rm.fileChannel.size(); 1256 long nbPages = fileSize / rm.pageSize; 1257 int nbPageBits = ( int ) ( nbPages / RecordManager.INT_SIZE ); 1258 1259 Map<String, int[]> checkedPages = new HashMap<String, int[]>( 2 ); 1260 1261 // The global page array 1262 checkedPages.put( GLOBAL_PAGES_NAME, new int[nbPageBits + 1] ); 1263 1264 // The freePages array 1265 checkedPages.put( FREE_PAGES_NAME, new int[nbPageBits + 1] ); 1266 1267 checkFreePages( rm, checkedPages ); 1268 break; 1269 1270 case 's': 1271 printFileSize(); 1272 break; 1273 1274 case 'd': 1275 check( rm ); 1276 break; 1277 1278 case 'r': 1279 loadRm(); 1280 break; 1281 1282 case 'o': 1283 readPageAt(); 1284 break; 1285 case 'q': 1286 stop = true; 1287 break; 1288 1289 default: 1290 System.out.println( "Invalid option" ); 1291 //c = readOption( br ); 1292 break; 1293 } 1294 } 1295 1296 try 1297 { 1298 rm.close(); 1299 br.close(); 1300 } 1301 catch ( Exception e ) 1302 { 1303 //ignore 1304 } 1305 } 1306 1307 1308 /** 1309 * Read the user's interaction 1310 */ 1311 private String readLine() 1312 { 1313 try 1314 { 1315 String line = br.readLine(); 1316 1317 if ( line != null ) 1318 { 1319 return line.trim(); 1320 } 1321 else 1322 { 1323 return ""; 1324 } 1325 } 1326 catch ( Exception e ) 1327 { 1328 throw new RuntimeException( e ); 1329 } 1330 } 1331 1332 1333 /** 1334 * Process the input and get back the selected choice 1335 */ 1336 private char readOption() 1337 { 1338 try 1339 { 1340 String s = br.readLine(); 1341 1342 if ( ( s == null ) || ( s.length() == 0 ) ) 1343 { 1344 return ' '; 1345 } 1346 1347 return s.charAt( 0 ); 1348 } 1349 catch ( Exception e ) 1350 { 1351 throw new RuntimeException( e ); 1352 } 1353 } 1354 1355 1356 private void readPageAt() throws IOException 1357 { 1358 System.out.println(); 1359 System.out.print( "Offset: " ); 1360 1361 String s = readLine(); 1362 1363 long offset = -1; 1364 1365 try 1366 { 1367 offset = Long.parseLong( s.trim() ); 1368 } 1369 catch( Exception e ) 1370 { 1371 offset = -1; 1372 } 1373 1374 if( offset < 0 || offset > (rm.fileChannel.size() - rm.DEFAULT_PAGE_SIZE) ) 1375 { 1376 System.out.println( "Invalid offset " + s ); 1377 return; 1378 } 1379 1380 PageIO io = rm.fetchPage( offset ); 1381 1382 List<Long> ll = new ArrayList<Long>(); 1383 ll.add( offset ); 1384 1385 do 1386 { 1387// System.out.println( "Next Page: " + next ); 1388// System.out.println( "Size: " + io.getSize() ); 1389// ByteBuffer data = io.getData(); 1390 1391 long next = io.getNextPage(); 1392 ll.add( next ); 1393 if ( next == -1 ) 1394 { 1395 break; 1396 } 1397 1398 io = rm.fetchPage( next ); 1399 } 1400 while( true ); 1401 1402 int i = 0; 1403 for ( ; i < ll.size() - 2; i++ ) 1404 { 1405 System.out.print( ll.get( i ) + " --> "); 1406 } 1407 1408 System.out.println( ll.get( i ) ); 1409 } 1410 1411 1412 /** 1413 * Main method 1414 */ 1415 public static void main( String[] args ) throws Exception 1416 { 1417 1418 if ( args.length == 0 ) 1419 { 1420 System.out.println( "Usage java MavibotInspector <db-file-path>" ); 1421 System.exit( 0 ); 1422 } 1423 1424 File f = new File( args[0] ); 1425 1426 MavibotInspector mi = new MavibotInspector( f ); 1427 mi.start(); 1428 } 1429} 1430 1431/** 1432 * A class used to store some information about the Btree 1433 */ 1434final class BtreeInfo<K, V> 1435{ 1436 // The btree name 1437 /* no qualifier */String btreeName; 1438 1439 // The key serializer 1440 /* no qualifier */ElementSerializer<K> keySerializer; 1441 1442 // The value serializer 1443 /* no qualifier */ElementSerializer<V> valueSerializer; 1444 1445 1446 public String toString() 1447 { 1448 StringBuilder sb = new StringBuilder(); 1449 1450 sb.append( "B-tree Info :" ); 1451 sb.append( "\n name : " ).append( btreeName ); 1452 sb.append( "\n key serializer : " ).append( keySerializer.getClass().getName() ); 1453 sb.append( "\n value serializer : " ).append( valueSerializer.getClass().getName() ); 1454 1455 return sb.toString(); 1456 } 1457}