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 010 * trunk/opends/resource/legal-notices/OpenDS.LICENSE 011 * or https://OpenDS.dev.java.net/OpenDS.LICENSE. 012 * See the License for the specific language governing permissions 013 * and limitations under the License. 014 * 015 * When distributing Covered Code, include this CDDL HEADER in each 016 * file and include the License file at 017 * trunk/opends/resource/legal-notices/OpenDS.LICENSE. If applicable, 018 * add the following below this CDDL HEADER, with the fields enclosed 019 * by brackets "[]" replaced with your own identifying information: 020 * Portions Copyright [yyyy] [name of copyright owner] 021 * 022 * CDDL HEADER END 023 * 024 * 025 * Copyright 2006-2008 Sun Microsystems, Inc. 026 */ 027 package org.opends.server.replication.plugin; 028 029 import java.util.ArrayList; 030 import java.util.Iterator; 031 import java.util.LinkedHashSet; 032 import java.util.Set; 033 034 import org.opends.server.replication.common.ChangeNumber; 035 import org.opends.server.types.Attribute; 036 import org.opends.server.types.AttributeType; 037 import org.opends.server.types.AttributeValue; 038 import org.opends.server.types.Entry; 039 import org.opends.server.types.Modification; 040 import org.opends.server.types.ModificationType; 041 042 043 /** 044 * This classes is used to store historical information for multiple valued 045 * attributes. 046 * One object of this type is created for each attribute that was changed in 047 * the entry. 048 * It allows to record the last time a given value was added, the last 049 * time a given value was deleted and the last time the whole attribute was 050 * deleted. 051 */ 052 public class AttrInfoMultiple extends AttributeInfo 053 { 054 private ChangeNumber deleteTime, // last time when the attribute was deleted 055 lastUpdateTime; // last time the attribute was modified 056 private ArrayList<ValueInfo> valuesInfo; // creation or deletion time for 057 // given values 058 /** 059 * create a new AttrInfo object. 060 * @param deleteTime the deletion time 061 * @param updateTime the update time 062 * @param valuesInfo of Value Info 063 */ 064 public AttrInfoMultiple(ChangeNumber deleteTime, ChangeNumber updateTime, 065 ArrayList<ValueInfo> valuesInfo) 066 { 067 this.deleteTime = deleteTime; 068 this.lastUpdateTime = updateTime; 069 if (valuesInfo == null) 070 this.valuesInfo = new ArrayList<ValueInfo>(); 071 else 072 this.valuesInfo = valuesInfo; 073 } 074 075 /** 076 * create a new empty AttrInfo object. 077 */ 078 public AttrInfoMultiple() 079 { 080 this.deleteTime = null; 081 this.lastUpdateTime = null; 082 this.valuesInfo = new ArrayList<ValueInfo>(); 083 } 084 085 /** 086 * Returns the last time when the entry was updated. 087 * @return the last time when the entry was updated 088 */ 089 private ChangeNumber getLastUpdateTime() 090 { 091 return lastUpdateTime; 092 } 093 094 /** 095 * Returns the last time when the attribute was deleted. 096 * 097 * @return the last time when the attribute was deleted 098 */ 099 public ChangeNumber getDeleteTime() 100 { 101 return deleteTime; 102 } 103 104 /** 105 * Duplicate an AttrInfo. 106 * ChangeNumber are duplicated by references 107 * @return the duplicated AttrInfo 108 */ 109 AttrInfoMultiple duplicate() 110 { 111 AttrInfoMultiple dup = 112 new AttrInfoMultiple(this.deleteTime, this.lastUpdateTime, 113 this.valuesInfo); 114 return dup; 115 } 116 117 /** 118 * Delete all historical information that is older than 119 * the provided ChangeNumber for this attribute type. 120 * Add the delete attribute state information 121 * @param CN time when the delete was done 122 */ 123 protected void delete(ChangeNumber CN) 124 { 125 // iterate through the values in the valuesInfo 126 // and suppress all the values that have not been added 127 // after the date of this delete. 128 Iterator<ValueInfo> it = this.valuesInfo.iterator(); 129 while (it.hasNext()) 130 { 131 ValueInfo info = it.next(); 132 if (CN.newerOrEquals(info.getValueUpdateTime())) 133 it.remove(); 134 } 135 136 if (CN.newer(deleteTime)) 137 { 138 deleteTime = CN; 139 } 140 141 if (CN.newer(lastUpdateTime)) 142 { 143 lastUpdateTime = CN; 144 } 145 } 146 147 /** 148 * Change historical information after a delete value. 149 * @param val value that was deleted 150 * @param CN time when the delete was done 151 */ 152 protected void delete(AttributeValue val, ChangeNumber CN) 153 { 154 ValueInfo info = new ValueInfo(val, null, CN); 155 this.valuesInfo.remove(info); 156 this.valuesInfo.add(info); 157 if (CN.newer(lastUpdateTime)) 158 { 159 lastUpdateTime = CN; 160 } 161 } 162 163 /** 164 * Change historical information after a delete of a set of values. 165 * 166 * @param values values that were deleted 167 * @param CN time when the delete was done 168 */ 169 protected void delete(LinkedHashSet<AttributeValue> values, ChangeNumber CN) 170 { 171 for (AttributeValue val : values) 172 { 173 ValueInfo info = new ValueInfo(val, null, CN); 174 this.valuesInfo.remove(info); 175 this.valuesInfo.add(info); 176 if (CN.newer(lastUpdateTime)) 177 { 178 lastUpdateTime = CN; 179 } 180 } 181 } 182 183 /** 184 * Update the historical information when a value is added. 185 * 186 * @param val values that was added 187 * @param CN time when the value was added 188 */ 189 protected void add(AttributeValue val, ChangeNumber CN) 190 { 191 ValueInfo info = new ValueInfo(val, CN, null); 192 this.valuesInfo.remove(info); 193 valuesInfo.add(info); 194 if (CN.newer(lastUpdateTime)) 195 { 196 lastUpdateTime = CN; 197 } 198 } 199 200 /** 201 * Update the historical information when values are added. 202 * 203 * @param values the set of added values 204 * @param CN time when the add is done 205 */ 206 private void add(LinkedHashSet<AttributeValue> values, 207 ChangeNumber CN) 208 { 209 for (AttributeValue val : values) 210 { 211 ValueInfo info = new ValueInfo(val, CN, null); 212 this.valuesInfo.remove(info); 213 valuesInfo.add(info); 214 if (CN.newer(lastUpdateTime)) 215 { 216 lastUpdateTime = CN; 217 } 218 } 219 } 220 221 /** 222 * Get the List of ValueInfo for this attribute Info. 223 * 224 * @return the List of ValueInfo 225 */ 226 public ArrayList<ValueInfo> getValuesInfo() 227 { 228 return valuesInfo; 229 } 230 231 /** 232 * {@inheritDoc} 233 */ 234 public boolean replayOperation( 235 Iterator<Modification> modsIterator, ChangeNumber changeNumber, 236 Entry modifiedEntry, Modification m) 237 { 238 // We are replaying an operation that was already done 239 // on another master server and this operation has a potential 240 // conflict 241 // with some more recent operations on this same entry 242 // we need to take the more complex path to solve them 243 Attribute modAttr = m.getAttribute(); 244 AttributeType type = modAttr.getAttributeType(); 245 246 if (ChangeNumber.compare(changeNumber, getLastUpdateTime()) <= 0) 247 { 248 // the attribute was modified after this change -> conflict 249 250 switch (m.getModificationType()) 251 { 252 case DELETE: 253 if (changeNumber.older(getDeleteTime())) 254 { 255 /* this delete is already obsoleted by a more recent delete 256 * skip this mod 257 */ 258 modsIterator.remove(); 259 break; 260 } 261 262 conflictDelete(changeNumber, type, m, modifiedEntry, modAttr); 263 break; 264 265 case ADD: 266 conflictAdd(modsIterator, changeNumber, 267 modAttr.getValues(), modAttr.getOptions()); 268 break; 269 270 case REPLACE: 271 if (changeNumber.older(getDeleteTime())) 272 { 273 /* this replace is already obsoleted by a more recent delete 274 * skip this mod 275 */ 276 modsIterator.remove(); 277 break; 278 } 279 /* save the values that are added by the replace operation 280 * into addedValues 281 * first process the replace as a delete operation -> this generate 282 * a list of values that should be kept 283 * then process the addedValues as if they were coming from a add 284 * -> this generate the list of values that needs to be added 285 * concatenate the 2 generated lists into a replace 286 */ 287 LinkedHashSet<AttributeValue> addedValues = modAttr.getValues(); 288 modAttr.setValues(new LinkedHashSet<AttributeValue>()); 289 290 this.conflictDelete(changeNumber, type, m, modifiedEntry, modAttr); 291 292 LinkedHashSet<AttributeValue> keptValues = modAttr.getValues(); 293 this.conflictAdd(modsIterator, changeNumber, addedValues, 294 modAttr.getOptions()); 295 keptValues.addAll(addedValues); 296 break; 297 298 case INCREMENT: 299 // TODO : FILL ME 300 break; 301 } 302 return true; 303 } 304 else 305 { 306 processLocalOrNonConflictModification(changeNumber, m); 307 return false;// the attribute was not modified more recently 308 } 309 } 310 311 /** 312 * This method calculate the historical information and update the hist 313 * attribute to store the historical information for modify operation that 314 * does not conflict with previous operation. 315 * This is the usual path and should therefore be optimized. 316 * 317 * It does not check if the operation to process is conflicting or not with 318 * previous operations. The caller is responsible for this. 319 * 320 * @param changeNumber The changeNumber of the operation to process 321 * @param mod The modify operation to process. 322 */ 323 public void processLocalOrNonConflictModification(ChangeNumber changeNumber, 324 Modification mod) 325 { 326 /* 327 * The operation is either a non-conflicting operation or a local 328 * operation so there is no need to check the historical information 329 * for conflicts. 330 * If this is a local operation, then this code is run after 331 * the pre-operation phase. 332 * If this is a non-conflicting replicated operation, this code is run 333 * during the handleConflictResolution(). 334 */ 335 336 Attribute modAttr = mod.getAttribute(); 337 AttributeType type = modAttr.getAttributeType(); 338 339 switch (mod.getModificationType()) 340 { 341 case DELETE: 342 if (modAttr.getValues().isEmpty()) 343 { 344 delete(changeNumber); 345 } 346 else 347 { 348 delete(modAttr.getValues(), changeNumber); 349 } 350 break; 351 352 case ADD: 353 if (type.isSingleValue()) 354 { 355 delete(changeNumber); 356 } 357 add(modAttr.getValues(), changeNumber); 358 break; 359 360 case REPLACE: 361 /* TODO : can we replace specific attribute values ????? */ 362 delete(changeNumber); 363 add(modAttr.getValues(), changeNumber); 364 break; 365 366 case INCREMENT: 367 /* FIXME : we should update ChangeNumber */ 368 break; 369 } 370 } 371 372 /** 373 * Process a delete attribute values that is conflicting with a previous 374 * modification. 375 * 376 * @param changeNumber The changeNumber of the currently processed change 377 * @param type attribute type 378 * @param m the modification that is being processed 379 * @param modifiedEntry the entry that is modified (before current mod) 380 * @param attrInfo the historical info associated to the entry 381 * @param modAttr the attribute modification 382 * @return false if there is nothing to do 383 */ 384 private boolean conflictDelete(ChangeNumber changeNumber, 385 AttributeType type, Modification m, 386 Entry modifiedEntry, 387 Attribute modAttr ) 388 { 389 LinkedHashSet<AttributeValue> delValues; 390 LinkedHashSet<AttributeValue> replValues; 391 392 /* 393 * We are processing a conflicting DELETE modification 394 * 395 * This code is written on the assumption that conflict are 396 * rare. We therefore don't care much about the performance 397 * However since it is rarely executed this code needs to be 398 * as simple as possible to make sure that all paths are tested. 399 * In this case the most simple seem to change the DELETE 400 * in a REPLACE modification that keeps all values 401 * more recent that the DELETE. 402 * we are therefore going to change m into a REPLACE that will keep 403 * all the values that have been updated after the DELETE time 404 * If a value is present in the entry without any state information 405 * it must be removed so we simply ignore them 406 */ 407 408 409 410 delValues = modAttr.getValues(); 411 if ((delValues == null) || (delValues.isEmpty())) 412 { 413 /* 414 * We are processing a DELETE attribute modification 415 */ 416 m.setModificationType(ModificationType.REPLACE); 417 replValues = new LinkedHashSet<AttributeValue>(); 418 419 for (Iterator it = getValuesInfo().iterator(); 420 it.hasNext();) 421 { 422 ValueInfo valInfo; valInfo = (ValueInfo) it.next(); 423 424 if (changeNumber.older(valInfo.getValueUpdateTime())) 425 { 426 /* 427 * this value has been updated after this delete, therefore 428 * this value must be kept 429 */ 430 replValues.add(valInfo.getValue()); 431 } 432 else 433 { 434 /* 435 * this value is going to be deleted, remove it from historical 436 * information unless it is a Deleted attribute value that is 437 * more recent than this DELETE 438 */ 439 if (changeNumber.newerOrEquals(valInfo.getValueDeleteTime())) 440 { 441 it.remove(); 442 } 443 } 444 } 445 446 modAttr.setValues(replValues); 447 if (changeNumber.newer(getDeleteTime())) 448 { 449 deleteTime = changeNumber; 450 } 451 if (changeNumber.newer(getLastUpdateTime())) 452 { 453 lastUpdateTime = changeNumber; 454 } 455 } 456 else 457 { 458 /* 459 * we are processing DELETE of some attribute values 460 */ 461 ArrayList<ValueInfo> valuesInfo = getValuesInfo(); 462 463 for (Iterator<AttributeValue> delValIterator = delValues.iterator(); 464 delValIterator.hasNext();) 465 { 466 AttributeValue val = delValIterator.next(); 467 Boolean deleteIt = true; // true if the delete must be done 468 469 /* update historical information */ 470 ValueInfo valInfo = new ValueInfo(val, null, changeNumber); 471 int index = valuesInfo.indexOf(valInfo); 472 if (index != -1) 473 { 474 /* this value already exist in the historical information */ 475 ValueInfo oldValInfo = valuesInfo.get(index); 476 if (changeNumber.newer(oldValInfo.getValueDeleteTime()) && 477 changeNumber.newer(oldValInfo.getValueUpdateTime())) 478 { 479 valuesInfo.remove(index); 480 valuesInfo.add(valInfo); 481 } 482 else if (oldValInfo.isUpdate()) 483 { 484 deleteIt = false; 485 } 486 } 487 else 488 { 489 valuesInfo.add(valInfo); 490 } 491 /* if the attribute value is not to be deleted 492 * or if attribute value is not present suppress it from the 493 * mod to make sure the delete is going to process again 494 */ 495 modifiedEntry.getAttribute(type); 496 if (!deleteIt 497 || !modifiedEntry.hasValue(type, modAttr.getOptions(), val)) 498 { 499 delValIterator.remove(); 500 } 501 } 502 if (changeNumber.newer(getLastUpdateTime())) 503 { 504 lastUpdateTime = changeNumber; 505 } 506 } 507 return true; 508 } 509 510 /** 511 * Process a add attribute values that is conflicting with a previous 512 * modification. 513 * 514 * @param modsIterator iterator on the list of modification 515 * @param changeNumber the historical info associated to the entry 516 * @param addValues the values that are added 517 * @param options the options that are added 518 * @return false if operation becomes empty and must not be processed 519 */ 520 private boolean conflictAdd(Iterator modsIterator, ChangeNumber changeNumber, 521 LinkedHashSet<AttributeValue> addValues, 522 Set<String> options) 523 { 524 /* if historicalattributedelete is newer forget this mod 525 * else find attr value 526 * if does not exist 527 * add historicalvalueadded timestamp 528 * add real value in entry 529 * else if timestamp older and already was historicalvalueadded 530 * update historicalvalueadded 531 * else if timestamp older and was historicalvaluedeleted 532 * change historicalvaluedeleted into historicalvalueadded 533 * add value in real entry 534 */ 535 536 if (changeNumber.older(getDeleteTime())) 537 { 538 /* A delete has been done more recently than this add 539 * forget this MOD ADD 540 */ 541 modsIterator.remove(); 542 return false; 543 } 544 545 for (Iterator<AttributeValue> valIterator = addValues.iterator(); 546 valIterator.hasNext();) 547 { 548 AttributeValue addVal= valIterator.next(); 549 ArrayList<ValueInfo> valuesInfo = getValuesInfo(); 550 ValueInfo valInfo = new ValueInfo(addVal, changeNumber, null); 551 int index = valuesInfo.indexOf(valInfo); 552 if (index == -1) 553 { 554 /* this values does not exist yet 555 * add it in the historical information 556 * let the operation process normally 557 */ 558 valuesInfo.add(valInfo); 559 } 560 else 561 { 562 ValueInfo oldValueInfo = valuesInfo.get(index); 563 if (oldValueInfo.isUpdate()) 564 { 565 /* if the value is already present 566 * check if the updateTime must be updated 567 * in all cases suppress this value from the value list 568 * as it is already present in the entry 569 */ 570 if (changeNumber.newer(oldValueInfo.getValueUpdateTime())) 571 { 572 valuesInfo.remove(index); 573 valuesInfo.add(valInfo); 574 } 575 valIterator.remove(); 576 } 577 else 578 { 579 /* this value is marked as a deleted value 580 * check if this mod is more recent the this delete 581 */ 582 if (changeNumber.newer(oldValueInfo.getValueDeleteTime())) 583 { 584 /* this add is more recent, 585 * remove the old delete historical information 586 * and add our more recent one 587 * let the operation process 588 */ 589 valuesInfo.remove(index); 590 valuesInfo.add(valInfo); 591 } 592 else 593 { 594 /* the delete that is present in the historical information 595 * is more recent so it must win, 596 * remove this value from the list of values to add 597 * don't update the historical information 598 */ 599 valIterator.remove(); 600 } 601 } 602 } 603 } 604 if (addValues.isEmpty()) 605 { 606 modsIterator.remove(); 607 } 608 609 if (changeNumber.newer(getLastUpdateTime())) 610 { 611 lastUpdateTime = changeNumber; 612 } 613 return true; 614 } 615 616 /** 617 * {@inheritDoc} 618 */ 619 @Override 620 public void load(HistKey histKey, AttributeValue value, ChangeNumber cn) 621 { 622 switch (histKey) 623 { 624 case ADD: 625 if (value != null) 626 { 627 add(value, cn); 628 } 629 break; 630 631 case DEL: 632 if (value != null) 633 { 634 delete(value, cn); 635 } 636 break; 637 638 case REPL: 639 delete(cn); 640 if (value != null) 641 { 642 add(value, cn); 643 } 644 break; 645 646 case DELATTR: 647 delete(cn); 648 break; 649 } 650 } 651 } 652 653