001/* 002 * CDDL HEADER START 003 * 004 * The contents of this file are subject to the terms of the 005 * Common Development and Distribution License, Version 1.0 only 006 * (the "License"). You may not use this file except in compliance 007 * with the License. 008 * 009 * You can obtain a copy of the license at legal-notices/CDDLv1_0.txt 010 * or http://forgerock.org/license/CDDLv1.0.html. 011 * See the License for the specific language governing permissions 012 * and limitations under the License. 013 * 014 * When distributing Covered Code, include this CDDL HEADER in each 015 * file and include the License file at legal-notices/CDDLv1_0.txt. 016 * If applicable, add the following below this CDDL HEADER, with the 017 * fields enclosed by brackets "[]" replaced with your own identifying 018 * information: 019 * Portions Copyright [yyyy] [name of copyright owner] 020 * 021 * CDDL HEADER END 022 * 023 * 024 * Copyright 2006-2008 Sun Microsystems, Inc. 025 * Portions Copyright 2011-2015 ForgeRock AS 026 */ 027package org.opends.server.backends.jeb; 028 029import static org.opends.messages.BackendMessages.*; 030import static org.opends.server.util.StaticUtils.*; 031 032import java.util.Iterator; 033import java.util.LinkedList; 034import java.util.List; 035import java.util.TreeSet; 036import java.util.concurrent.atomic.AtomicInteger; 037 038import org.forgerock.i18n.LocalizableMessage; 039import org.forgerock.i18n.slf4j.LocalizedLogger; 040import org.forgerock.opendj.config.server.ConfigChangeResult; 041import org.forgerock.opendj.config.server.ConfigException; 042import org.forgerock.opendj.ldap.ByteSequence; 043import org.forgerock.opendj.ldap.ByteString; 044import org.forgerock.opendj.ldap.ByteStringBuilder; 045import org.forgerock.opendj.ldap.DecodeException; 046import org.forgerock.opendj.ldap.ResultCode; 047import org.forgerock.opendj.ldap.SearchScope; 048import org.forgerock.opendj.ldap.schema.MatchingRule; 049import org.opends.server.admin.server.ConfigurationChangeListener; 050import org.opends.server.admin.std.meta.LocalDBVLVIndexCfgDefn.Scope; 051import org.opends.server.admin.std.server.LocalDBVLVIndexCfg; 052import org.opends.server.controls.ServerSideSortRequestControl; 053import org.opends.server.controls.VLVRequestControl; 054import org.opends.server.controls.VLVResponseControl; 055import org.opends.server.core.DirectoryServer; 056import org.opends.server.core.SearchOperation; 057import org.opends.server.protocols.ldap.LDAPResultCode; 058import org.opends.server.types.Attribute; 059import org.opends.server.types.AttributeType; 060import org.opends.server.types.DN; 061import org.opends.server.types.DirectoryException; 062import org.opends.server.types.Entry; 063import org.opends.server.types.Modification; 064import org.opends.server.types.SearchFilter; 065import org.opends.server.types.SortKey; 066import org.opends.server.types.SortOrder; 067import org.opends.server.util.StaticUtils; 068 069import com.sleepycat.je.*; 070 071/** 072 * This class represents a VLV index. Each database record is a sorted list 073 * of entry IDs followed by sets of attribute values used to sort the entries. 074 * The entire set of entry IDs are broken up into sorted subsets to decrease 075 * the number of database retrievals needed for a range lookup. The records are 076 * keyed by the last entry's first sort attribute value. The list of entries 077 * in a particular database record maintains the property where the first sort 078 * attribute value is bigger then the previous key but smaller or equal 079 * to its own key. 080 */ 081public class VLVIndex extends DatabaseContainer 082 implements ConfigurationChangeListener<LocalDBVLVIndexCfg> 083{ 084 private static final LocalizedLogger logger = LocalizedLogger.getLoggerForThisClass(); 085 086 /** The comparator for vlvIndex keys. */ 087 public VLVKeyComparator comparator; 088 /** The limit on the number of entry IDs that may be indexed by one key. */ 089 private int sortedSetCapacity = 4000; 090 /** The SortOrder in use by this VLV index to sort the entries. */ 091 public SortOrder sortOrder; 092 093 /** The cached count of entries in this index. */ 094 private final AtomicInteger count; 095 096 private final State state; 097 /** 098 * A flag to indicate if this vlvIndex should be trusted to be consistent 099 * with the entries database. 100 */ 101 private boolean trusted; 102 103 /** The VLV vlvIndex configuration. */ 104 private LocalDBVLVIndexCfg config; 105 106 private DN baseDN; 107 private SearchFilter filter; 108 private SearchScope scope; 109 110 111 /** 112 * Create a new VLV vlvIndex object. 113 * 114 * @param config The VLV index config object to use for this VLV 115 * index. 116 * @param state The state database to persist vlvIndex state info. 117 * @param env The JE Environment 118 * @param entryContainer The database entryContainer holding this vlvIndex. 119 * @throws com.sleepycat.je.DatabaseException 120 * If an error occurs in the JE database. 121 * @throws ConfigException if a error occurs while reading the VLV index 122 * configuration 123 */ 124 VLVIndex(LocalDBVLVIndexCfg config, State state, Environment env, EntryContainer entryContainer) 125 throws DatabaseException, ConfigException 126 { 127 super(entryContainer.getDatabasePrefix()+"_vlv."+config.getName(), 128 env, entryContainer); 129 130 this.config = config; 131 this.baseDN = config.getBaseDN(); 132 this.scope = convertScope(config.getScope()); 133 this.sortedSetCapacity = config.getMaxBlockSize(); 134 135 try 136 { 137 this.filter = SearchFilter.createFilterFromString(config.getFilter()); 138 } 139 catch(Exception e) 140 { 141 throw new ConfigException(ERR_CONFIG_VLV_INDEX_BAD_FILTER.get( 142 config.getFilter(), name, stackTraceToSingleLineString(e))); 143 } 144 145 String[] sortAttrs = config.getSortOrder().split(" "); 146 SortKey[] sortKeys = new SortKey[sortAttrs.length]; 147 MatchingRule[] orderingRules = new MatchingRule[sortAttrs.length]; 148 boolean[] ascending = new boolean[sortAttrs.length]; 149 for(int i = 0; i < sortAttrs.length; i++) 150 { 151 try 152 { 153 if(sortAttrs[i].startsWith("-")) 154 { 155 ascending[i] = false; 156 sortAttrs[i] = sortAttrs[i].substring(1); 157 } 158 else 159 { 160 ascending[i] = true; 161 if(sortAttrs[i].startsWith("+")) 162 { 163 sortAttrs[i] = sortAttrs[i].substring(1); 164 } 165 } 166 } 167 catch(Exception e) 168 { 169 throw new ConfigException(ERR_CONFIG_VLV_INDEX_UNDEFINED_ATTR.get(sortKeys[i], name)); 170 } 171 172 AttributeType attrType = 173 DirectoryServer.getAttributeType(sortAttrs[i].toLowerCase()); 174 if(attrType == null) 175 { 176 throw new ConfigException(ERR_CONFIG_VLV_INDEX_UNDEFINED_ATTR.get(sortAttrs[i], name)); 177 } 178 sortKeys[i] = new SortKey(attrType, ascending[i]); 179 orderingRules[i] = attrType.getOrderingMatchingRule(); 180 } 181 182 this.sortOrder = new SortOrder(sortKeys); 183 this.comparator = new VLVKeyComparator(orderingRules, ascending); 184 185 this.dbConfig = JEBUtils.toDatabaseConfigNoDuplicates(env); 186 this.dbConfig.setOverrideBtreeComparator(true); 187 this.dbConfig.setBtreeComparator(this.comparator); 188 189 this.state = state; 190 191 this.trusted = state.getIndexTrustState(null, this); 192 if (!trusted && entryContainer.getHighestEntryID().longValue() == 0) 193 { 194 // If there are no entries in the entry container then there 195 // is no reason why this vlvIndex can't be upgraded to trusted. 196 setTrusted(null, true); 197 } 198 199 this.count = new AtomicInteger(0); 200 this.config.addChangeListener(this); 201 } 202 203 private SearchScope convertScope(final Scope cfgScope) 204 { 205 switch (cfgScope) 206 { 207 case BASE_OBJECT: 208 return SearchScope.BASE_OBJECT; 209 case SINGLE_LEVEL: 210 return SearchScope.SINGLE_LEVEL; 211 case SUBORDINATE_SUBTREE: 212 return SearchScope.SUBORDINATES; 213 default: // WHOLE_SUBTREE 214 return SearchScope.WHOLE_SUBTREE; 215 } 216 } 217 218 /** {@inheritDoc} */ 219 @Override 220 public void open() throws DatabaseException 221 { 222 super.open(); 223 224 DatabaseEntry key = new DatabaseEntry(); 225 DatabaseEntry data = new DatabaseEntry(); 226 LockMode lockMode = LockMode.RMW; 227 228 Cursor cursor = openCursor(null, CursorConfig.READ_COMMITTED); 229 try 230 { 231 OperationStatus status = cursor.getFirst(key, data,lockMode); 232 while(status == OperationStatus.SUCCESS) 233 { 234 count.getAndAdd(SortValuesSet.getEncodedSize(data.getData(), 0)); 235 status = cursor.getNext(key, data, lockMode); 236 } 237 } 238 finally 239 { 240 cursor.close(); 241 } 242 } 243 244 /** 245 * Close the VLV index. 246 * 247 * @throws DatabaseException if a JE database error occurs while 248 * closing the index. 249 */ 250 @Override 251 public void close() throws DatabaseException 252 { 253 super.close(); 254 this.config.removeChangeListener(this); 255 } 256 257 /** 258 * Update the vlvIndex for a new entry. 259 * 260 * @param txn A database transaction, or null if none is required. 261 * @param entryID The entry ID. 262 * @param entry The entry to be indexed. 263 * @return True if the entry ID for the entry are added. False if 264 * the entry ID already exists. 265 * @throws DatabaseException If an error occurs in the JE database. 266 * @throws org.opends.server.types.DirectoryException If a Directory Server 267 * error occurs. 268 * @throws JebException If an error occurs in the JE backend. 269 */ 270 public boolean addEntry(Transaction txn, EntryID entryID, Entry entry) 271 throws DatabaseException, DirectoryException, JebException 272 { 273 return shouldInclude(entry) 274 && insertValues(txn, entryID.longValue(), entry); 275 } 276 277 /** 278 * Update the vlvIndex for a new entry. 279 * 280 * @param buffer The index buffer to buffer the changes. 281 * @param entryID The entry ID. 282 * @param entry The entry to be indexed. 283 * @return True if the entry ID for the entry are added. False if 284 * the entry ID already exists. 285 * @throws DirectoryException If a Directory Server 286 * error occurs. 287 */ 288 boolean addEntry(IndexBuffer buffer, EntryID entryID, Entry entry) throws DirectoryException 289 { 290 if (shouldInclude(entry)) 291 { 292 final SortValues sortValues = new SortValues(entryID, entry, sortOrder); 293 buffer.getVLVIndex(this).addValues(sortValues); 294 return true; 295 } 296 return false; 297 } 298 299 /** 300 * Update the vlvIndex for a deleted entry. 301 * 302 * @param buffer The database transaction to be used for the deletions 303 * @param entryID The entry ID 304 * @param entry The contents of the deleted entry. 305 * @return True if the entry was successfully removed from this VLV index 306 * or False otherwise. 307 * @throws DirectoryException If a Directory Server error occurs. 308 */ 309 boolean removeEntry(IndexBuffer buffer, EntryID entryID, Entry entry) throws DirectoryException 310 { 311 if (shouldInclude(entry)) 312 { 313 final SortValues sortValues = new SortValues(entryID, entry, sortOrder); 314 buffer.getVLVIndex(this).deleteValues(sortValues); 315 return true; 316 } 317 return false; 318 } 319 320 /** 321 * Update the vlvIndex to reflect a sequence of modifications in a Modify 322 * operation. 323 * 324 * @param buffer The database transaction to be used for the deletions 325 * @param entryID The ID of the entry that was modified. 326 * @param oldEntry The entry before the modifications were applied. 327 * @param newEntry The entry after the modifications were applied. 328 * @param mods The sequence of modifications in the Modify operation. 329 * @return True if the modification was successfully processed or False 330 * otherwise. 331 * @throws DatabaseException If an error occurs during an operation on a 332 * JE database. 333 * @throws DirectoryException If a Directory Server error occurs. 334 */ 335 boolean modifyEntry(IndexBuffer buffer, 336 EntryID entryID, 337 Entry oldEntry, 338 Entry newEntry, 339 List<Modification> mods) 340 throws DatabaseException, DirectoryException 341 { 342 if (shouldInclude(oldEntry)) 343 { 344 if (shouldInclude(newEntry)) 345 { 346 // The entry should still be indexed. See if any sorted attributes are changed. 347 if (isSortAttributeModified(mods)) 348 { 349 // Sorted attributes have changed. Reindex the entry; 350 boolean success; 351 success = removeEntry(buffer, entryID, oldEntry); 352 success &= addEntry(buffer, entryID, newEntry); 353 return success; 354 } 355 } 356 else 357 { 358 // The modifications caused the new entry to be unindexed. 359 return removeEntry(buffer, entryID, oldEntry); 360 } 361 } 362 else 363 { 364 if (shouldInclude(newEntry)) 365 { 366 // The modifications caused the new entry to be indexed. Add to vlvIndex 367 return addEntry(buffer, entryID, newEntry); 368 } 369 } 370 371 // The modifications does not affect this vlvIndex 372 return true; 373 } 374 375 private boolean isSortAttributeModified(List<Modification> mods) 376 { 377 for (SortKey sortKey : sortOrder.getSortKeys()) 378 { 379 AttributeType attributeType = sortKey.getAttributeType(); 380 List<AttributeType> subTypes = DirectoryServer.getSchema().getSubTypes(attributeType); 381 for (Modification mod : mods) 382 { 383 AttributeType modAttrType = mod.getAttribute().getAttributeType(); 384 if (modAttrType.equals(attributeType) 385 || subTypes.contains(modAttrType)) 386 { 387 return true; 388 } 389 } 390 } 391 return false; 392 } 393 394 /** 395 * Get a sorted values set that should contain the entry with the given 396 * information. 397 * 398 * @param txn The transaction to use when retrieving the set or NULL if it is 399 * not required. 400 * @param entryID The entry ID to use. 401 * @param values The values to use. 402 * @param types The types of the values to use. 403 * @return The SortValuesSet that should contain the entry with the given 404 * information. 405 * @throws DatabaseException If an error occurs during an operation on a 406 * JE database. 407 * @throws DirectoryException If a Directory Server error occurs. 408 */ 409 SortValuesSet getSortValuesSet(Transaction txn, long entryID, 410 ByteString[] values, AttributeType[] types) throws DatabaseException, 411 DirectoryException 412 { 413 DatabaseEntry key = new DatabaseEntry(encodeKey(entryID, values, types)); 414 DatabaseEntry data = new DatabaseEntry(); 415 return getSortValuesSet(txn, key, data, LockMode.DEFAULT); 416 } 417 418 private SortValuesSet getSortValuesSet(Transaction txn, DatabaseEntry key, 419 DatabaseEntry data, LockMode lockMode) 420 { 421 OperationStatus status = getSearchKeyRange(txn, key, data, lockMode); 422 if (status != OperationStatus.SUCCESS) 423 { 424 // There are no records in the database 425 if (logger.isTraceEnabled()) 426 { 427 logger.trace("No sort values set exist in VLV vlvIndex %s. " 428 + "Creating unbound set.", config.getName()); 429 } 430 // this could not be found, so clean the key for later reuse 431 key.setData(new byte[0]); 432 return new SortValuesSet(this); 433 } 434 435 if (logger.isTraceEnabled()) 436 { 437 logSearchKeyResult(key); 438 } 439 return new SortValuesSet(key.getData(), data.getData(), this); 440 } 441 442 private void logSearchKeyResult(DatabaseEntry key) 443 { 444 StringBuilder searchKeyHex = new StringBuilder(); 445 StaticUtils.byteArrayToHexPlusAscii(searchKeyHex, key.getData(), 4); 446 StringBuilder foundKeyHex = new StringBuilder(); 447 StaticUtils.byteArrayToHexPlusAscii(foundKeyHex, key.getData(), 4); 448 logger.trace("Retrieved a sort values set in VLV vlvIndex %s\n" + 449 "Search Key:%s\nFound Key:%s\n", 450 config.getName(), searchKeyHex, foundKeyHex); 451 } 452 453 /** 454 * Search for entries matching the entry ID and attribute values and 455 * return its entry ID. 456 * 457 * @param txn The JE transaction to use for database updates. 458 * @param entryID The entry ID to search for. 459 * @param values The values to search for. 460 * @param types The types of the values to search for. 461 * @return The index of the entry ID matching the values or -1 if its not 462 * found. 463 * @throws DatabaseException If an error occurs during an operation on a 464 * JE database. 465 * @throws JebException If an error occurs during an operation on a 466 * JE database. 467 * @throws DirectoryException If a Directory Server error occurs. 468 */ 469 boolean containsValues(Transaction txn, long entryID, 470 ByteString[] values, AttributeType[] types) throws JebException, 471 DatabaseException, DirectoryException 472 { 473 SortValuesSet valuesSet = getSortValuesSet(txn, entryID, values, types); 474 int pos = valuesSet.binarySearch(entryID, values); 475 return pos >= 0; 476 } 477 478 private boolean insertValues(Transaction txn, long entryID, Entry entry) 479 throws JebException, DatabaseException, DirectoryException 480 { 481 ByteString[] values = getSortValues(entry); 482 AttributeType[] types = getSortTypes(); 483 DatabaseEntry key = new DatabaseEntry(encodeKey(entryID, values, types)); 484 DatabaseEntry data = new DatabaseEntry(); 485 486 SortValuesSet sortValuesSet = 487 getSortValuesSet(txn, key, data, LockMode.RMW); 488 boolean success = sortValuesSet.add(entryID, values, types); 489 490 int newSize = sortValuesSet.size(); 491 if(newSize >= sortedSetCapacity) 492 { 493 SortValuesSet splitSortValuesSet = sortValuesSet.split(newSize / 2); 494 put(txn, key, data, splitSortValuesSet); // splitAfter 495 put(txn, key, data, sortValuesSet); // after 496 497 if(logger.isTraceEnabled()) 498 { 499 logger.trace("SortValuesSet with key %s has reached" + 500 " the entry size of %d. Spliting into two sets with " + 501 " keys %s and %s.", splitSortValuesSet.getKeySortValues(), 502 newSize, sortValuesSet.getKeySortValues(), 503 splitSortValuesSet.getKeySortValues()); 504 } 505 } 506 else 507 { 508 data.setData(sortValuesSet.toDatabase()); // after 509 put(txn, key, data); 510 // TODO: What about phantoms? 511 } 512 513 if(success) 514 { 515 count.getAndIncrement(); 516 } 517 518 return success; 519 } 520 521 private void put(Transaction txn, DatabaseEntry key, DatabaseEntry data, 522 SortValuesSet set) throws DirectoryException 523 { 524 key.setData(set.getKeyBytes()); 525 data.setData(set.toDatabase()); 526 put(txn, key, data); 527 } 528 529 /** 530 * Gets the types of the attribute values to sort. 531 * 532 * @return The types of the attribute values to sort on. 533 */ 534 AttributeType[] getSortTypes() 535 { 536 SortKey[] sortKeys = sortOrder.getSortKeys(); 537 AttributeType[] types = new AttributeType[sortKeys.length]; 538 for (int i = 0; i < sortKeys.length; i++) 539 { 540 types[i] = sortKeys[i].getAttributeType(); 541 } 542 return types; 543 } 544 545 private OperationStatus getSearchKeyRange(Transaction txn, DatabaseEntry key, 546 DatabaseEntry data, LockMode lockMode) 547 { 548 Cursor cursor = openCursor(txn, CursorConfig.READ_COMMITTED); 549 try 550 { 551 return cursor.getSearchKeyRange(key, data, lockMode); 552 } 553 finally 554 { 555 cursor.close(); 556 } 557 } 558 559 /** 560 * Update the vlvIndex with the specified values to add and delete. 561 * 562 * @param txn A database transaction, or null if none is required. 563 * @param addedValues The values to add to the VLV index. 564 * @param deletedValues The values to delete from the VLV index. 565 * @throws DatabaseException If an error occurs in the JE database. 566 * @throws DirectoryException If a Directory Server 567 * error occurs. 568 */ 569 void updateIndex(Transaction txn, TreeSet<SortValues> addedValues, TreeSet<SortValues> deletedValues) 570 throws DirectoryException, DatabaseException 571 { 572 // Handle cases where nothing is changed early to avoid 573 // DB access. 574 if((addedValues == null || addedValues.isEmpty()) && 575 (deletedValues == null || deletedValues.isEmpty())) 576 { 577 return; 578 } 579 580 DatabaseEntry key = new DatabaseEntry(); 581 DatabaseEntry data = new DatabaseEntry(); 582 Iterator<SortValues> aValues = null; 583 Iterator<SortValues> dValues = null; 584 SortValues av = null; 585 SortValues dv = null; 586 587 if(addedValues != null) 588 { 589 aValues = addedValues.iterator(); 590 av = aValues.next(); 591 } 592 if(deletedValues != null) 593 { 594 dValues = deletedValues.iterator(); 595 dv = dValues.next(); 596 } 597 598 while(true) 599 { 600 if(av != null) 601 { 602 if(dv != null) 603 { 604 // Start from the smallest values from either set. 605 if(av.compareTo(dv) < 0) 606 { 607 key.setData(encodeKey(av)); 608 } 609 else 610 { 611 key.setData(encodeKey(dv)); 612 } 613 } 614 else 615 { 616 key.setData(encodeKey(av)); 617 } 618 } 619 else if(dv != null) 620 { 621 key.setData(encodeKey(dv)); 622 } 623 else 624 { 625 break; 626 } 627 628 final SortValuesSet sortValuesSet = getSortValuesSet(txn, key, data, LockMode.RMW); 629 int oldSize = sortValuesSet.size(); 630 if(key.getData().length == 0) 631 { 632 // This is the last unbounded set. 633 while(av != null) 634 { 635 sortValuesSet.add(av); 636 av = moveToNextSortValues(aValues); 637 } 638 639 while(dv != null) 640 { 641 sortValuesSet.remove(dv); 642 dv = moveToNextSortValues(dValues); 643 } 644 } 645 else 646 { 647 SortValues maxValues = decodeKey(sortValuesSet.getKeyBytes()); 648 649 while(av != null && av.compareTo(maxValues) <= 0) 650 { 651 sortValuesSet.add(av); 652 av = moveToNextSortValues(aValues); 653 } 654 655 while(dv != null && dv.compareTo(maxValues) <= 0) 656 { 657 sortValuesSet.remove(dv); 658 dv = moveToNextSortValues(dValues); 659 } 660 } 661 662 int newSize = sortValuesSet.size(); 663 if(newSize >= sortedSetCapacity) 664 { 665 SortValuesSet splitSortValuesSet = sortValuesSet.split(newSize / 2); 666 put(txn, key, data, splitSortValuesSet); // splitAfter 667 put(txn, key, data, sortValuesSet); // after 668 669 if(logger.isTraceEnabled()) 670 { 671 logger.trace("SortValuesSet with key %s has reached" + 672 " the entry size of %d. Spliting into two sets with " + 673 " keys %s and %s.", splitSortValuesSet.getKeySortValues(), 674 newSize, sortValuesSet.getKeySortValues(), 675 splitSortValuesSet.getKeySortValues()); 676 } 677 } 678 else if(newSize == 0) 679 { 680 delete(txn, key); 681 } 682 else 683 { 684 byte[] after = sortValuesSet.toDatabase(); 685 data.setData(after); 686 put(txn, key, data); 687 } 688 689 count.getAndAdd(newSize - oldSize); 690 } 691 } 692 693 private SortValues moveToNextSortValues(Iterator<SortValues> sortValues) 694 { 695 sortValues.remove(); 696 if (sortValues.hasNext()) 697 { 698 return sortValues.next(); 699 } 700 return null; 701 } 702 703 private byte[] encodeKey(SortValues sv) throws DirectoryException 704 { 705 return encodeKey(sv.getEntryID(), sv.getValues(), sv.getTypes()); 706 } 707 708 /** 709 * Evaluate a search with sort control using this VLV index. 710 * 711 * @param txn The transaction to used when reading the index or NULL if it is 712 * not required. 713 * @param searchOperation The search operation to evaluate. 714 * @param sortControl The sort request control to evaluate. 715 * @param vlvRequest The VLV request control to evaluate or NULL if VLV is not 716 * requested. 717 * @param debugBuilder If not null, a diagnostic string will be written 718 * which will help determine how this index contributed 719 * to this search. 720 * @return The sorted EntryIDSet containing the entry IDs that match the 721 * search criteria. 722 * @throws DirectoryException If a Directory Server error occurs. 723 * @throws DatabaseException If an error occurs in the JE database. 724 */ 725 EntryIDSet evaluate(Transaction txn, 726 SearchOperation searchOperation, 727 ServerSideSortRequestControl sortControl, 728 VLVRequestControl vlvRequest, 729 StringBuilder debugBuilder) 730 throws DirectoryException, DatabaseException 731 { 732 if (!trusted 733 || !searchOperation.getBaseDN().equals(baseDN) 734 || !searchOperation.getScope().equals(scope) 735 || !searchOperation.getFilter().equals(filter) 736 || !sortControl.getSortOrder().equals(sortOrder)) 737 { 738 return null; 739 } 740 741 if (debugBuilder != null) 742 { 743 debugBuilder.append("vlv="); 744 debugBuilder.append("[INDEX:"); 745 debugBuilder.append(name.replace(entryContainer.getDatabasePrefix() + "_", "")); 746 debugBuilder.append("]"); 747 } 748 749 long[] selectedIDs = new long[0]; 750 if(vlvRequest != null) 751 { 752 int currentCount = count.get(); 753 int beforeCount = vlvRequest.getBeforeCount(); 754 int afterCount = vlvRequest.getAfterCount(); 755 756 if (vlvRequest.getTargetType() == VLVRequestControl.TYPE_TARGET_BYOFFSET) 757 { 758 int targetOffset = vlvRequest.getOffset(); 759 if (targetOffset < 0) 760 { 761 // The client specified a negative target offset. This should never 762 // be allowed. 763 searchOperation.addResponseControl( 764 new VLVResponseControl(targetOffset, currentCount, 765 LDAPResultCode.OFFSET_RANGE_ERROR)); 766 767 LocalizableMessage message = ERR_ENTRYIDSORTER_NEGATIVE_START_POS.get(); 768 throw new DirectoryException(ResultCode.VIRTUAL_LIST_VIEW_ERROR, 769 message); 770 } 771 else if (targetOffset == 0) 772 { 773 // This is an easy mistake to make, since VLV offsets start at 1 774 // instead of 0. We'll assume the client meant to use 1. 775 targetOffset = 1; 776 } 777 int listOffset = targetOffset - 1; // VLV offsets start at 1, not 0. 778 int startPos = listOffset - beforeCount; 779 if (startPos < 0) 780 { 781 // This can happen if beforeCount >= offset, and in this case we'll 782 // just adjust the start position to ignore the range of beforeCount 783 // that doesn't exist. 784 startPos = 0; 785 beforeCount = listOffset; 786 } 787 else if(startPos >= currentCount) 788 { 789 // The start position is beyond the end of the list. In this case, 790 // we'll assume that the start position was one greater than the 791 // size of the list and will only return the beforeCount entries. 792 // The start position is beyond the end of the list. In this case, 793 // we'll assume that the start position was one greater than the 794 // size of the list and will only return the beforeCount entries. 795 targetOffset = currentCount + 1; 796 listOffset = currentCount; 797 startPos = listOffset - beforeCount; 798 afterCount = 0; 799 } 800 801 int count = 1 + beforeCount + afterCount; 802 selectedIDs = new long[count]; 803 804 Cursor cursor = openCursor(txn, CursorConfig.READ_COMMITTED); 805 try 806 { 807 DatabaseEntry key = new DatabaseEntry(); 808 DatabaseEntry data = new DatabaseEntry(); 809 LockMode lockMode = LockMode.DEFAULT; 810 //Locate the set that contains the target entry. 811 int cursorCount = 0; 812 int selectedPos = 0; 813 OperationStatus status = cursor.getFirst(key, data, lockMode); 814 while(status == OperationStatus.SUCCESS) 815 { 816 if(logger.isTraceEnabled()) 817 { 818 logSearchKeyResult(key); 819 } 820 long[] IDs = SortValuesSet.getEncodedIDs(data.getData(), 0); 821 for(int i = startPos + selectedPos - cursorCount; 822 i < IDs.length && selectedPos < count; 823 i++, selectedPos++) 824 { 825 selectedIDs[selectedPos] = IDs[i]; 826 } 827 cursorCount += IDs.length; 828 status = cursor.getNext(key, data,lockMode); 829 } 830 831 if (selectedPos < count) 832 { 833 // We don't have enough entries in the set to meet the requested 834 // page size, so we'll need to shorten the array. 835 long[] newIDArray = new long[selectedPos]; 836 System.arraycopy(selectedIDs, 0, newIDArray, 0, selectedPos); 837 selectedIDs = newIDArray; 838 } 839 840 searchOperation.addResponseControl( 841 new VLVResponseControl(targetOffset, currentCount, 842 LDAPResultCode.SUCCESS)); 843 844 if(debugBuilder != null) 845 { 846 debugBuilder.append("[COUNT:"); 847 debugBuilder.append(cursorCount); 848 debugBuilder.append("]"); 849 } 850 } 851 finally 852 { 853 cursor.close(); 854 } 855 } 856 else 857 { 858 int targetOffset = 0; 859 int includedBeforeCount = 0; 860 int includedAfterCount = 0; 861 LinkedList<EntryID> idList = new LinkedList<>(); 862 DatabaseEntry key = new DatabaseEntry(); 863 DatabaseEntry data = new DatabaseEntry(); 864 865 Cursor cursor = openCursor(txn, CursorConfig.READ_COMMITTED); 866 try 867 { 868 LockMode lockMode = LockMode.DEFAULT; 869 ByteSequence vBytes = vlvRequest.getGreaterThanOrEqualAssertion(); 870 ByteStringBuilder keyBytes = 871 new ByteStringBuilder(vBytes.length() + 4); 872 keyBytes.appendBERLength(vBytes.length()); 873 vBytes.copyTo(keyBytes); 874 875 key.setData(keyBytes.getBackingArray(), 0, keyBytes.length()); 876 OperationStatus status = cursor.getSearchKeyRange(key, data, lockMode); 877 if(status == OperationStatus.SUCCESS) 878 { 879 if(logger.isTraceEnabled()) 880 { 881 logSearchKeyResult(key); 882 } 883 SortValuesSet sortValuesSet = 884 new SortValuesSet(key.getData(), data.getData(), this); 885 886 int adjustedTargetOffset = sortValuesSet.binarySearch( 887 -1, vlvRequest.getGreaterThanOrEqualAssertion()); 888 if(adjustedTargetOffset < 0) 889 { 890 // For a negative return value r, the vlvIndex -(r+1) gives the 891 // array index of the ID that is greater then the assertion value. 892 adjustedTargetOffset = -(adjustedTargetOffset+1); 893 } 894 895 targetOffset = adjustedTargetOffset; 896 897 // Iterate through all the sort values sets before this one to find 898 // the target offset in the index. 899 int lastOffset = adjustedTargetOffset - 1; 900 long[] lastIDs = sortValuesSet.getEntryIDs(); 901 while(true) 902 { 903 for(int i = lastOffset; 904 i >= 0 && includedBeforeCount < beforeCount; i--) 905 { 906 idList.addFirst(new EntryID(lastIDs[i])); 907 includedBeforeCount++; 908 } 909 910 status = cursor.getPrev(key, data, lockMode); 911 if(status != OperationStatus.SUCCESS) 912 { 913 break; 914 } 915 916 if(includedBeforeCount < beforeCount) 917 { 918 lastIDs = SortValuesSet.getEncodedIDs(data.getData(), 0); 919 lastOffset = lastIDs.length - 1; 920 targetOffset += lastIDs.length; 921 } 922 else 923 { 924 targetOffset += SortValuesSet.getEncodedSize(data.getData(), 0); 925 } 926 } 927 928 929 // Set the cursor back to the position of the target entry set 930 key.setData(sortValuesSet.getKeyBytes()); 931 cursor.getSearchKey(key, data, lockMode); 932 933 // Add the target and after count entries if the target was found. 934 lastOffset = adjustedTargetOffset; 935 lastIDs = sortValuesSet.getEntryIDs(); 936 int afterIDCount = 0; 937 while(true) 938 { 939 for(int i = lastOffset; 940 i < lastIDs.length && includedAfterCount < afterCount + 1; 941 i++) 942 { 943 idList.addLast(new EntryID(lastIDs[i])); 944 includedAfterCount++; 945 } 946 947 if(includedAfterCount >= afterCount + 1) 948 { 949 break; 950 } 951 952 status = cursor.getNext(key, data, lockMode); 953 if(status != OperationStatus.SUCCESS) 954 { 955 break; 956 } 957 958 lastIDs = SortValuesSet.getEncodedIDs(data.getData(), 0); 959 lastOffset = 0; 960 afterIDCount += lastIDs.length; 961 } 962 963 selectedIDs = new long[idList.size()]; 964 Iterator<EntryID> idIterator = idList.iterator(); 965 for (int i=0; i < selectedIDs.length; i++) 966 { 967 selectedIDs[i] = idIterator.next().longValue(); 968 } 969 970 searchOperation.addResponseControl( 971 new VLVResponseControl(targetOffset + 1, currentCount, 972 LDAPResultCode.SUCCESS)); 973 974 if(debugBuilder != null) 975 { 976 debugBuilder.append("[COUNT:"); 977 debugBuilder.append(targetOffset + afterIDCount + 1); 978 debugBuilder.append("]"); 979 } 980 } 981 } 982 finally 983 { 984 cursor.close(); 985 } 986 } 987 } 988 else 989 { 990 LinkedList<long[]> idSets = new LinkedList<>(); 991 int currentCount = 0; 992 DatabaseEntry key = new DatabaseEntry(); 993 DatabaseEntry data = new DatabaseEntry(); 994 995 Cursor cursor = openCursor(txn, CursorConfig.READ_COMMITTED); 996 try 997 { 998 LockMode lockMode = LockMode.RMW; 999 OperationStatus status = cursor.getFirst(key, data, lockMode); 1000 while(status == OperationStatus.SUCCESS) 1001 { 1002 if(logger.isTraceEnabled()) 1003 { 1004 logSearchKeyResult(key); 1005 } 1006 long[] ids = SortValuesSet.getEncodedIDs(data.getData(), 0); 1007 idSets.add(ids); 1008 currentCount += ids.length; 1009 status = cursor.getNext(key, data, lockMode); 1010 } 1011 } 1012 finally 1013 { 1014 cursor.close(); 1015 } 1016 1017 selectedIDs = new long[currentCount]; 1018 int pos = 0; 1019 for(long[] id : idSets) 1020 { 1021 System.arraycopy(id, 0, selectedIDs, pos, id.length); 1022 pos += id.length; 1023 } 1024 1025 if(debugBuilder != null) 1026 { 1027 debugBuilder.append("[COUNT:"); 1028 debugBuilder.append(currentCount); 1029 debugBuilder.append("]"); 1030 } 1031 } 1032 return new EntryIDSet(selectedIDs, 0, selectedIDs.length); 1033 } 1034 1035 /** 1036 * Set the vlvIndex trust state. 1037 * @param txn A database transaction, or null if none is required. 1038 * @param trusted True if this vlvIndex should be trusted or false 1039 * otherwise. 1040 * @throws DatabaseException If an error occurs in the JE database. 1041 */ 1042 public synchronized void setTrusted(Transaction txn, boolean trusted) 1043 throws DatabaseException 1044 { 1045 this.trusted = trusted; 1046 state.putIndexTrustState(txn, this, trusted); 1047 } 1048 1049 /** 1050 * Return true iff this index is trusted. 1051 * @return the trusted state of this index 1052 */ 1053 public boolean isTrusted() 1054 { 1055 return trusted; 1056 } 1057 1058 /** 1059 * Gets the values to sort on from the entry. 1060 * 1061 * @param entry The entry to get the values from. 1062 * @return The attribute values to sort on. 1063 */ 1064 ByteString[] getSortValues(Entry entry) 1065 { 1066 SortKey[] sortKeys = sortOrder.getSortKeys(); 1067 ByteString[] values = new ByteString[sortKeys.length]; 1068 for (int i=0; i < sortKeys.length; i++) 1069 { 1070 SortKey sortKey = sortKeys[i]; 1071 List<Attribute> attrList = entry.getAttribute(sortKey.getAttributeType()); 1072 if (attrList != null) 1073 { 1074 // There may be multiple versions of this attribute in the target entry 1075 // (e.g., with different sets of options), and it may also be a 1076 // multivalued attribute. In that case, we need to find the value that 1077 // is the best match for the corresponding sort key (i.e., for sorting 1078 // in ascending order, we want to find the lowest value; for sorting in 1079 // descending order, we want to find the highest value). This is 1080 // handled by the SortKey.compareValues method. 1081 ByteString sortValue = null; 1082 for (Attribute a : attrList) 1083 { 1084 for (ByteString v : a) 1085 { 1086 if (sortValue == null || sortKey.compareValues(v, sortValue) < 0) 1087 { 1088 sortValue = v; 1089 } 1090 } 1091 } 1092 1093 values[i] = sortValue; 1094 } 1095 } 1096 return values; 1097 } 1098 1099 /** 1100 * Encode a VLV database key with the given information. 1101 * 1102 * @param entryID The entry ID to encode. 1103 * @param values The values to encode. 1104 * @param types The types of the values to encode. 1105 * @return The encoded bytes. 1106 * @throws DirectoryException If a Directory Server error occurs. 1107 */ 1108 byte[] encodeKey(long entryID, ByteString[] values, AttributeType[] types) 1109 throws DirectoryException 1110 { 1111 try 1112 { 1113 final ByteStringBuilder builder = new ByteStringBuilder(); 1114 1115 for (int i = 0; i < values.length; i++) 1116 { 1117 final ByteString v = values[i]; 1118 if (v == null) 1119 { 1120 builder.appendBERLength(0); 1121 } 1122 else 1123 { 1124 final MatchingRule eqRule = types[i].getEqualityMatchingRule(); 1125 final ByteString nv = eqRule.normalizeAttributeValue(v); 1126 builder.appendBERLength(nv.length()); 1127 builder.append(nv); 1128 } 1129 } 1130 builder.append(entryID); 1131 builder.trimToSize(); 1132 1133 return builder.getBackingArray(); 1134 } 1135 catch (DecodeException e) 1136 { 1137 throw new DirectoryException( 1138 ResultCode.INVALID_ATTRIBUTE_SYNTAX, e.getMessageObject(), e); 1139 } 1140 } 1141 1142 /** 1143 * Decode a VLV database key. 1144 * 1145 * @param keyBytes The byte array to decode. 1146 * @return The sort values represented by the key bytes. 1147 * @throws DirectoryException If a Directory Server error occurs. 1148 */ 1149 private SortValues decodeKey(byte[] keyBytes) throws DirectoryException 1150 { 1151 if(keyBytes == null || keyBytes.length == 0) 1152 { 1153 return null; 1154 } 1155 1156 ByteString[] attributeValues = new ByteString[sortOrder.getSortKeys().length]; 1157 int vBytesPos = 0; 1158 1159 for(int i = 0; i < attributeValues.length; i++) 1160 { 1161 int valueLength = keyBytes[vBytesPos] & 0x7F; 1162 if (valueLength != keyBytes[vBytesPos++]) 1163 { 1164 int valueLengthBytes = valueLength; 1165 valueLength = 0; 1166 for (int j=0; j < valueLengthBytes; j++, vBytesPos++) 1167 { 1168 valueLength = (valueLength << 8) | (keyBytes[vBytesPos] & 0xFF); 1169 } 1170 } 1171 1172 if(valueLength == 0) 1173 { 1174 attributeValues[i] = null; 1175 } 1176 else 1177 { 1178 byte[] valueBytes = new byte[valueLength]; 1179 System.arraycopy(keyBytes, vBytesPos, valueBytes, 0, valueLength); 1180 attributeValues[i] = ByteString.wrap(valueBytes); 1181 } 1182 1183 vBytesPos += valueLength; 1184 } 1185 1186 final long id = JebFormat.toLong(keyBytes, vBytesPos, keyBytes.length); 1187 return new SortValues(new EntryID(id), attributeValues, sortOrder); 1188 } 1189 1190 /** 1191 * Get the sorted set capacity configured for this VLV index. 1192 * 1193 * @return The sorted set capacity. 1194 */ 1195 public int getSortedSetCapacity() 1196 { 1197 return sortedSetCapacity; 1198 } 1199 1200 /** 1201 * Indicates if the given entry should belong in this VLV index. 1202 * 1203 * @param entry The entry to check. 1204 * @return True if the given entry should belong in this VLV index or False 1205 * otherwise. 1206 * @throws DirectoryException If a Directory Server error occurs. 1207 */ 1208 boolean shouldInclude(Entry entry) throws DirectoryException 1209 { 1210 DN entryDN = entry.getName(); 1211 return entryDN.matchesBaseAndScope(baseDN, scope) 1212 && filter.matchesEntry(entry); 1213 } 1214 1215 /** {@inheritDoc} */ 1216 @Override 1217 public synchronized boolean isConfigurationChangeAcceptable( 1218 LocalDBVLVIndexCfg cfg, 1219 List<LocalizableMessage> unacceptableReasons) 1220 { 1221 try 1222 { 1223 this.filter = SearchFilter.createFilterFromString(cfg.getFilter()); 1224 } 1225 catch(Exception e) 1226 { 1227 unacceptableReasons.add(ERR_CONFIG_VLV_INDEX_BAD_FILTER.get( 1228 cfg.getFilter(), name, stackTraceToSingleLineString(e))); 1229 return false; 1230 } 1231 1232 String[] sortAttrs = cfg.getSortOrder().split(" "); 1233 SortKey[] sortKeys = new SortKey[sortAttrs.length]; 1234 MatchingRule[] orderingRules = new MatchingRule[sortAttrs.length]; 1235 boolean[] ascending = new boolean[sortAttrs.length]; 1236 for(int i = 0; i < sortAttrs.length; i++) 1237 { 1238 try 1239 { 1240 if(sortAttrs[i].startsWith("-")) 1241 { 1242 ascending[i] = false; 1243 sortAttrs[i] = sortAttrs[i].substring(1); 1244 } 1245 else 1246 { 1247 ascending[i] = true; 1248 if(sortAttrs[i].startsWith("+")) 1249 { 1250 sortAttrs[i] = sortAttrs[i].substring(1); 1251 } 1252 } 1253 } 1254 catch(Exception e) 1255 { 1256 unacceptableReasons.add(ERR_CONFIG_VLV_INDEX_UNDEFINED_ATTR.get(sortKeys[i], name)); 1257 return false; 1258 } 1259 1260 AttributeType attrType = DirectoryServer.getAttributeType(sortAttrs[i].toLowerCase()); 1261 if(attrType == null) 1262 { 1263 unacceptableReasons.add(ERR_CONFIG_VLV_INDEX_UNDEFINED_ATTR.get(sortAttrs[i], name)); 1264 return false; 1265 } 1266 sortKeys[i] = new SortKey(attrType, ascending[i]); 1267 orderingRules[i] = attrType.getOrderingMatchingRule(); 1268 } 1269 1270 return true; 1271 } 1272 1273 /** {@inheritDoc} */ 1274 @Override 1275 public synchronized ConfigChangeResult applyConfigurationChange( 1276 LocalDBVLVIndexCfg cfg) 1277 { 1278 final ConfigChangeResult ccr = new ConfigChangeResult(); 1279 1280 // Update base DN only if changed.. 1281 if(!config.getBaseDN().equals(cfg.getBaseDN())) 1282 { 1283 this.baseDN = cfg.getBaseDN(); 1284 ccr.setAdminActionRequired(true); 1285 } 1286 1287 // Update scope only if changed. 1288 if(!config.getScope().equals(cfg.getScope())) 1289 { 1290 this.scope = convertScope(cfg.getScope()); 1291 ccr.setAdminActionRequired(true); 1292 } 1293 1294 // Update sort set capacity only if changed. 1295 if (config.getMaxBlockSize() != cfg.getMaxBlockSize()) 1296 { 1297 this.sortedSetCapacity = cfg.getMaxBlockSize(); 1298 1299 // Require admin action only if the new capacity is larger. Otherwise, 1300 // we will lazyly update the sorted sets. 1301 if (config.getMaxBlockSize() < cfg.getMaxBlockSize()) 1302 { 1303 ccr.setAdminActionRequired(true); 1304 } 1305 } 1306 1307 // Update the filter only if changed. 1308 if(!config.getFilter().equals(cfg.getFilter())) 1309 { 1310 try 1311 { 1312 this.filter = SearchFilter.createFilterFromString(cfg.getFilter()); 1313 ccr.setAdminActionRequired(true); 1314 } 1315 catch(Exception e) 1316 { 1317 ccr.addMessage(ERR_CONFIG_VLV_INDEX_BAD_FILTER.get(config.getFilter(), name, stackTraceToSingleLineString(e))); 1318 ccr.setResultCodeIfSuccess(ResultCode.INVALID_ATTRIBUTE_SYNTAX); 1319 } 1320 } 1321 1322 // Update the sort order only if changed. 1323 if (!config.getSortOrder().equals(cfg.getSortOrder())) 1324 { 1325 String[] sortAttrs = cfg.getSortOrder().split(" "); 1326 SortKey[] sortKeys = new SortKey[sortAttrs.length]; 1327 MatchingRule[] orderingRules = new MatchingRule[sortAttrs.length]; 1328 boolean[] ascending = new boolean[sortAttrs.length]; 1329 for(int i = 0; i < sortAttrs.length; i++) 1330 { 1331 try 1332 { 1333 if(sortAttrs[i].startsWith("-")) 1334 { 1335 ascending[i] = false; 1336 sortAttrs[i] = sortAttrs[i].substring(1); 1337 } 1338 else 1339 { 1340 ascending[i] = true; 1341 if(sortAttrs[i].startsWith("+")) 1342 { 1343 sortAttrs[i] = sortAttrs[i].substring(1); 1344 } 1345 } 1346 } 1347 catch(Exception e) 1348 { 1349 ccr.addMessage(ERR_CONFIG_VLV_INDEX_UNDEFINED_ATTR.get(sortKeys[i], name)); 1350 ccr.setResultCodeIfSuccess(ResultCode.INVALID_ATTRIBUTE_SYNTAX); 1351 } 1352 1353 AttributeType attrType = 1354 DirectoryServer.getAttributeType(sortAttrs[i].toLowerCase()); 1355 if(attrType == null) 1356 { 1357 ccr.addMessage(ERR_CONFIG_VLV_INDEX_UNDEFINED_ATTR.get(sortKeys[i], name)); 1358 ccr.setResultCodeIfSuccess(ResultCode.INVALID_ATTRIBUTE_SYNTAX); 1359 } 1360 else 1361 { 1362 sortKeys[i] = new SortKey(attrType, ascending[i]); 1363 orderingRules[i] = attrType.getOrderingMatchingRule(); 1364 } 1365 } 1366 1367 this.sortOrder = new SortOrder(sortKeys); 1368 this.comparator = new VLVKeyComparator(orderingRules, ascending); 1369 1370 // We have to close the database and open it using the new comparator. 1371 entryContainer.exclusiveLock.lock(); 1372 try 1373 { 1374 close(); 1375 this.dbConfig.setBtreeComparator(this.comparator); 1376 open(); 1377 } 1378 catch(DatabaseException de) 1379 { 1380 ccr.addMessage(LocalizableMessage.raw(StaticUtils.stackTraceToSingleLineString(de))); 1381 ccr.setResultCodeIfSuccess(DirectoryServer.getServerErrorResultCode()); 1382 } 1383 finally 1384 { 1385 entryContainer.exclusiveLock.unlock(); 1386 } 1387 1388 ccr.setAdminActionRequired(true); 1389 } 1390 1391 1392 if (ccr.adminActionRequired()) 1393 { 1394 trusted = false; 1395 ccr.addMessage(NOTE_INDEX_ADD_REQUIRES_REBUILD.get(name)); 1396 try 1397 { 1398 state.putIndexTrustState(null, this, false); 1399 } 1400 catch(DatabaseException de) 1401 { 1402 ccr.addMessage(LocalizableMessage.raw(StaticUtils.stackTraceToSingleLineString(de))); 1403 ccr.setResultCodeIfSuccess(DirectoryServer.getServerErrorResultCode()); 1404 } 1405 } 1406 1407 this.config = cfg; 1408 return ccr; 1409 } 1410}